We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
If you use a min heap and a max heap you can solve this in n*log(m) time.
1. Given n integers. min and max sum of m values needed.
2. Create a min heap and a max heap of m values.
3. Iterate over n-m values updating both the heaps everytime in log(m) operations.
4. After the iteration just sum the two heaps in o(m) time each.
Total time:
(n-m) * 2 * log(m) + 2 * m
~ (2n - 2m) * log(m)
~ n*log(m)
= O(nlog(m))
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Mini-Max Sum
You are viewing a single comment's thread. Return to all comments →
If you use a min heap and a max heap you can solve this in n*log(m) time. 1. Given n integers. min and max sum of m values needed. 2. Create a min heap and a max heap of m values. 3. Iterate over n-m values updating both the heaps everytime in log(m) operations. 4. After the iteration just sum the two heaps in o(m) time each.
Total time:
(n-m) * 2 * log(m) + 2 * m
~ (2n - 2m) * log(m) ~ n*log(m)
= O(nlog(m))