✅ C++ Must know Min/Max Heap Algo Intuition | Explained in Hindi
It was an interesting challenge, The same concept has been used in multiple Leetcode medium/hard challenges.\nThe min/max heap algo to find top k sums.\n\nMy th
It was an interesting challenge, The same concept has been used in multiple Leetcode medium/hard challenges.\nThe min/max heap algo to find top k sums.\n\nMy thought process with code below:\n\n    1. Naive solution: Number of subsequences that can be created by N sized array are\n    2^N (each element can be considered/not considered 2 choices for N elements)\n    Now if we create these 2^N elements and find sum of each of them and then sort\n    them to get the kth largest subsequence sum. O(N*2^N)\n    \n    2. N constraint is 10^5 so we definitely need a better solution.\n    Hold on folks, we are going deep :) \n    One **IMPT point is that input can have -ive numbers also.\n    \n    3. Another **IMPT point is that from k constraints can be max 2000, which means\n    that we can store the top k elements in a heap/multiset structure.\n   \n    4.So the maximum sum that we can have is sum of all +ive values. that is 1 sum.\n    we have to find k sum.\n    \n    5. Another way of seeing this is that once we have max sum = all positive integers\n    sum the total sum can only decrease after that. So if we take absolute value of\n    elements and find kth smallest sum of that array we can subtract that from total\n    to get kth maximum sum of array.\n    \n    6. Question boils down to finding kth minimum subsequence sum. we sort the absolute \n    array, start by considering 1st element and moving forward we have 2 options: take minimum\n    value from priority queue(sum, cur_index), and consider 2 combinations:\n    a. take index+1 value along with current sum\n    b. remove index value and consider index+1\n    now we can pop top of queue and insert value in our min vector. Do this until we reach size of\n    min set = k. Now we can find the kth minimal sum from this array.\n    \n    Also store current index, which we need to consider to remove the current element.\n    ex. nums = [2, 4, -2]\n    max sum = 6 = k = 1 sum\n    sorted(abs(nums)) = [2, 2, 4] 5th smallest subsequence sum\n    queue = (2, 0) min_sum_values = [0]\n    queue = (2 + 2, 1) (2+2-2, 1) = (4, 1), (2, 1) min_sum_values = [0, 2]\n    queue = (2+4, 2) (2+4-2, 2) (2, 1) = (4, 1) (4, 2) (6, 2) min_sum_values = [0, 2, 2]\n    queue = (8, 3) (4+4-4, 3) (4, 2) (6, 2) = min_sum_values = [0, 2, 2, 4]\n    queue = (4, 2) (4, 3) (6, 2) (8,3)= min_sum_values = [0, 2, 2, 4, 4]\n    min_sum_values[k-1] = 4\n    ans = 6-4 = 2\n\n    yay finally solved.\n    time complexity = NlogN(sorting the nums) + KlogK(addition and removal from priority queue)\n    space = O(K)\n\t\n\t\n\tIf you prefer video explanation: Please refer https://youtu.be/Jv_Oe3GjfzQ\n\n
[]