Find the K-Sum of an Array - Practice Coding Problems

Find the K-Sum of an Array - 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: The empty subsequence is considered to have a sum of 0.

Input & Output

Example 1 — Basic Case

$ Input: nums = [2,4,-2], k = 5

› Output: 2

💡 Note: All subsequence sums in descending order: [6,4,4,2,2,0,-2,-2], so the 5th largest is 2

Example 2 — All Positive

$ Input: nums = [1,1,1], k = 3

› Output: 2

💡 Note: Subsequence sums: [3,2,2,2,1,1,1,0], so the 3rd largest is 2

Example 3 — Mixed Numbers

$ Input: nums = [5,-2,1], k = 3

› Output: 1

💡 Note: Subsequence sums sorted: [6,4,3,1,1,-1,-2,-2], the 3rd largest is 1

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁵ ≤ nums[i] ≤ 10⁵
1 ≤ k ≤ min(2000, 2^nums.length)

Visualization

Tap to expand

Understanding the Visualization

Input

Array [2,4,-2] and k=5

Generate Sums

All subsequence sums: [6,4,4,2,2,0,-2,-2]

Find K-th

5th largest sum = 2

Key Takeaway

🎯 Key Insight: Transform the problem using positive/negative separation and generate sums efficiently with a priority queue

Asked in

G Google 25 a Amazon 18 M Microsoft 15 f Meta 12

The key insight is to transform the problem by separating positive and negative numbers, then use a priority queue to generate the k largest subsequence sums efficiently. Best approach uses heap-based state generation with Time: O(k log k), Space: O(k).

Common Approaches

Approach	Time	Space	Notes
✓ Priority Queue with State Generation	O(k × log k)	O(k)	Use max-heap to generate k largest sums on-demand without generating all subsequences
Generate All Subsequences	O(2ⁿ × n + 2ⁿ × log(2ⁿ))	O(2ⁿ)	Generate all 2^n subsequences, sort their sums, return kth largest

Priority Queue with State Generation — Algorithm Steps

Transform: add positive numbers, subtract negatives from max sum
Use max-heap starting with maximum possible sum
For each state, generate two new states: include/exclude next element
Extract k-th maximum sum

Visualization

Tap to expand

Step-by-Step Walkthrough

Transform

Separate positive and negative numbers, sort them

Heap Process

Use max-heap starting with maximum sum

Generate States

For each state, create new states by including/excluding elements

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_HEAP_SIZE 100000

typedef struct {
    long long sum;
    int posIdx, negIdx;
} State;

typedef struct {
    State data[MAX_HEAP_SIZE];
    int size;
} MaxHeap;

void heapifyUp(MaxHeap* h, int idx) {
    while (idx > 0) {
        int parent = (idx - 1) / 2;
        if (h->data[parent].sum >= h->data[idx].sum) break;
        State temp = h->data[parent];
        h->data[parent] = h->data[idx];
        h->data[idx] = temp;
        idx = parent;
    }
}

void heapifyDown(MaxHeap* h, int idx) {
    while (2 * idx + 1 < h->size) {
        int maxIdx = idx;
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        
        if (h->data[left].sum > h->data[maxIdx].sum) maxIdx = left;
        if (right < h->size && h->data[right].sum > h->data[maxIdx].sum) maxIdx = right;
        
        if (maxIdx == idx) break;
        State temp = h->data[idx];
        h->data[idx] = h->data[maxIdx];
        h->data[maxIdx] = temp;
        idx = maxIdx;
    }
}

void push(MaxHeap* h, State s) {
    h->data[h->size] = s;
    heapifyUp(h, h->size);
    h->size++;
}

State pop(MaxHeap* h) {
    State result = h->data[0];
    h->data[0] = h->data[--h->size];
    heapifyDown(h, 0);
    return result;
}

long long solution(int* nums, int n, int k) {
    int pos[n], neg[n];
    int posSize = 0, negSize = 0;
    
    for (int i = 0; i < n; i++) {
        if (nums[i] > 0) pos[posSize++] = nums[i];
        else if (nums[i] < 0) neg[negSize++] = -nums[i];
    }
    
    // Sort pos in descending order
    for (int i = 0; i < posSize - 1; i++) {
        for (int j = i + 1; j < posSize; j++) {
            if (pos[i] < pos[j]) {
                int temp = pos[i]; pos[i] = pos[j]; pos[j] = temp;
            }
        }
    }
    
    // Sort neg in ascending order
    for (int i = 0; i < negSize - 1; i++) {
        for (int j = i + 1; j < negSize; j++) {
            if (neg[i] > neg[j]) {
                int temp = neg[i]; neg[i] = neg[j]; neg[j] = temp;
            }
        }
    }
    
    long long maxSum = 0;
    for (int i = 0; i < posSize; i++) maxSum += pos[i];
    
    MaxHeap h = {.size = 0};
    State initial = {maxSum, 0, 0};
    push(&h, initial);
    
    int seen[1000][2] = {0}; // Simple seen set for small inputs
    int seenCount = 0;
    seen[seenCount][0] = 0;
    seen[seenCount++][1] = 0;
    
    for (int i = 0; i < k; i++) {
        State current = pop(&h);
        
        if (i == k - 1) return current.sum;
        
        if (current.posIdx < posSize) {
            int found = 0;
            for (int j = 0; j < seenCount; j++) {
                if (seen[j][0] == current.posIdx + 1 && seen[j][1] == current.negIdx) {
                    found = 1; break;
                }
            }
            if (!found) {
                seen[seenCount][0] = current.posIdx + 1;
                seen[seenCount++][1] = current.negIdx;
                State newState = {current.sum - pos[current.posIdx], current.posIdx + 1, current.negIdx};
                push(&h, newState);
            }
        }
        
        if (current.negIdx < negSize) {
            int found = 0;
            for (int j = 0; j < seenCount; j++) {
                if (seen[j][0] == current.posIdx && seen[j][1] == current.negIdx + 1) {
                    found = 1; break;
                }
            }
            if (!found) {
                seen[seenCount][0] = current.posIdx;
                seen[seenCount++][1] = current.negIdx + 1;
                State newState = {current.sum - neg[current.negIdx], current.posIdx, current.negIdx + 1};
                push(&h, newState);
            }
        }
    }
    
    return 0;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[20];
    int n = 0;
    char* token = strtok(line, "[],\n ");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, "[],\n ");
    }
    
    int k;
    scanf("%d", &k);
    
    printf("%lld\n", solution(nums, n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k × log k)

Extract k elements from heap, each operation takes O(log k) time

⚡ Linearithmic

Space Complexity

O(k)

Heap stores at most k states at any time

✓ Linear Space

23.4K Views

Medium Frequency

~35 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Priority Queue with State Generation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler