Heap | Java | Find "Smallest"
A pretty difficult problem I think. Here is how I solved it during the contest: \n\nFirst, I consider only the case where the array contains positive integers o
A pretty difficult problem I think. Here is how I solved it during the contest: \n\nFirst, I consider only the case where the array contains positive integers only. It is obviously that we can find the `k`th smallest subsequence and subtract it from sum of all (positive) elements. Second, I consider the case when negative elements mixed in. We have 2 options to decrease the max sum. Either include a biggest negative number or exclud the smallest positive number. In either cases, the sum will be reduced by its absolute value. \n\nSo, I add up all positive values. Sort it, and make all negative elements positive. But I think here is the difficult part.\nHow do we find the `k`th smallest subsequence? I consider heap, and we just need a way such that we iterate through all the subsequence somehow. \nso, consider the smallest element `{0}`, we can split it like so\n\n`{0} -> {0, 1} and {1}`\n`{1} -> {1, 2} and {2}`\n`{0, 1} -> {0, 1, 2} and {0, 2}`\n`{a, a+1, a+2, ..., a+k} -> {a, a+1, a+2, ..., a+k, a+k+1} and {a, a+1, a+2, ..., a+k+1}`\nIn short, heap item ending in `a_k` spliting into 2 subsequences, both ending in `a_(k+1)` but one with `a_k` and the other without. \nIt\'s a tree where 2 children are at least as large as its parent.\n\n`Time O(nlogn + KlogK)`\n`Space O(K)`\n```Java\nclass Solution {\n    public long kSum(int[] nums, int k) {\n        long minus = 0, all = 0;\n        for (int i = 0; i < nums.length; i++){\n            all += Math.max(nums[i], 0); // take all positive values \n            nums[i] = Math.abs(nums[i]); // make all non-negative\n        }\n        Arrays.sort(nums); // sort it\n        var minheap = new PriorityQueue<long[]>(Comparator.comparingLong(o -> o[0]));\n        minheap.offer(new long[]{nums[0], 0});\n        while(--k>0){ // construct the smallest subsequence value in a smart way\n            long[] top = minheap.poll();\n            int i = (int)top[1]++;\n            long val = top[0];\n            minus = val;\n            if (i < nums.length-1){ // each item (node) branches out into 2 (children)\n                top[0] += nums[i+1];\n                minheap.offer(new long[]{val - nums[i] + nums[i+1], i+1});\n                minheap.offer(top);\n            }\n        }\n        return all - minus;\n    }\n}\n```
['Heap (Priority Queue)', 'Java']