Formatted question description: https://leetcode.ca/all/2386.html

2386. Find the K-Sum of an Array

Difficulty: Hard.
Related Topics: Array, Sorting, Heap (Priority Queue).
Similar Questions: .

Problem

You are given an integer array nums and a positive integer k. You can choose any subsequence of the array and sum all of its elements together.

We define the K-Sum of the array as the kth largest subsequence sum that can be obtained (not necessarily distinct).

Return the K-Sum of the array.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Note that the empty subsequence is considered to have a sum of 0.

Example 1:

Input: nums = [2,4,-2], k = 5
Output: 2
Explanation: All the possible subsequence sums that we can obtain are the following sorted in decreasing order:
- 6, 4, 4, 2, 2, 0, 0, -2.
The 5-Sum of the array is 2.

Example 2:

Input: nums = [1,-2,3,4,-10,12], k = 16
Output: 10
Explanation: The 16-Sum of the array is 10.

Constraints:

n == nums.length
1 <= n <= 105
-109 <= nums[i] <= 109
1 <= k <= min(2000, 2n)

Solution

class Solution {
    public long kSum(int[] nums, int k) {
        long sum = 0L;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                sum += nums[i];
            } else {
                nums[i] = -nums[i];
            }
        }
        Arrays.sort(nums);
        PriorityQueue<Pair<Long, Integer>> pq =
                new PriorityQueue<>((a, b) -> Long.compare(b.getKey(), a.getKey()));
        pq.offer(new Pair<>(sum, 0));
        while (k-- > 1) {
            Pair<Long, Integer> top = pq.poll();
            long s = top.getKey();
            int i = top.getValue();
            if (i < nums.length) {
                pq.offer(new Pair<>(s - nums[i], i + 1));
                if (i > 0) {
                    pq.offer(new Pair<>(s - nums[i] + nums[i - 1], i + 1));
                }
            }
        }
        return pq.peek().getKey();
    }

    private static class Pair<K, V> {
        K key;
        V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }
    }
}

############

class Solution {
    public long kSum(int[] nums, int k) {
        long mx = 0;
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                mx += nums[i];
            } else {
                nums[i] *= -1;
            }
        }
        Arrays.sort(nums);
        PriorityQueue<Pair<Long, Integer>> pq
            = new PriorityQueue<>(Comparator.comparing(Pair::getKey));
        pq.offer(new Pair<>(0L, 0));
        while (--k > 0) {
            var p = pq.poll();
            long s = p.getKey();
            int i = p.getValue();
            if (i < n) {
                pq.offer(new Pair<>(s + nums[i], i + 1));
                if (i > 0) {
                    pq.offer(new Pair<>(s + nums[i] - nums[i - 1], i + 1));
                }
            }
        }
        return mx - pq.peek().getKey();
    }
}

class Solution:
    def kSum(self, nums: List[int], k: int) -> int:
        mx = 0
        for i, v in enumerate(nums):
            if v > 0:
                mx += v
            else:
                nums[i] = -v
        nums.sort()
        h = [(0, 0)]
        for _ in range(k - 1):
            s, i = heappop(h)
            if i < len(nums):
                heappush(h, (s + nums[i], i + 1))
                if i:
                    heappush(h, (s + nums[i] - nums[i - 1], i + 1))
        return mx - h[0][0]

############

# 2386. Find the K-Sum of an Array
# https://leetcode.com/problems/find-the-k-sum-of-an-array

class Solution:
    def kSum(self, nums: List[int], k: int) -> int:
        N = len(nums)
        posSum = sum(x for x in nums if x > 0)
        A = sorted(abs(x) for x in nums)
        res = posSum
        maxHeap = [(-posSum + A[0], 0)]

        for _ in range(k - 1):
            nextSum, index = heappop(maxHeap)

            if index + 1 < N:
                # -(-nextSum - A[index + 1])
                heappush(maxHeap, (nextSum + A[index + 1], index + 1))
                # -(-nextSum + A[index] - A[index + 1])
                heappush(maxHeap, (nextSum - A[index] + A[index + 1], index + 1))
            
            res = -nextSum
        
        return res

using pli = pair<long long, int>;

class Solution {
public:
    long long kSum(vector<int>& nums, int k) {
        long long mx = 0;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (nums[i] > 0) {
                mx += nums[i];
            } else {
                nums[i] *= -1;
            }
        }
        sort(nums.begin(), nums.end());
        priority_queue<pli, vector<pli>, greater<pli>> pq;
        pq.push({0, 0});
        while (--k) {
            auto p = pq.top();
            pq.pop();
            long long s = p.first;
            int i = p.second;
            if (i < n) {
                pq.push({s + nums[i], i + 1});
                if (i) {
                    pq.push({s + nums[i] - nums[i - 1], i + 1});
                }
            }
        }
        return mx - pq.top().first;
    }
};

func kSum(nums []int, k int) int64 {
	mx := 0
	for i, v := range nums {
		if v > 0 {
			mx += v
		} else {
			nums[i] *= -1
		}
	}
	sort.Ints(nums)
	h := &hp{ {0, 0} }
	for k > 1 {
		k--
		p := heap.Pop(h).(pair)
		if p.i < len(nums) {
			heap.Push(h, pair{p.sum + nums[p.i], p.i + 1})
			if p.i > 0 {
				heap.Push(h, pair{p.sum + nums[p.i] - nums[p.i-1], p.i + 1})
			}
		}
	}
	return int64(mx) - int64((*h)[0].sum)
}

type pair struct{ sum, i int }
type hp []pair

func (h hp) Len() int            { return len(h) }
func (h hp) Less(i, j int) bool  { return h[i].sum < h[j].sum }
func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

Explain:

nope.

Complexity:

Time complexity : O(n).
Space complexity : O(n).

2386 - Find the K-Sum of an Array

2386. Find the K-Sum of an Array

Problem

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

2386. Find the K-Sum of an Array

Problem

Solution

All Problems

All Solutions