Kth Smallest Subarray Sum - Practice Coding Problems

Kth Smallest Subarray Sum - Problem

Given an integer array nums of length n and an integer k, return the kth smallest subarray sum.

A subarray is defined as a non-empty contiguous sequence of elements in an array. A subarray sum is the sum of all elements in the subarray.

Note: Subarrays are ordered by their sum values in ascending order. If two subarrays have the same sum, they are considered equal for ranking purposes.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: All subarrays: [2]→2, [2,1]→3, [2,1,3]→6, [1]→1, [1,3]→4, [3]→3. Sorted sums: [1,2,3,3,4,6]. The 4th smallest is 3.

Example 2 — Small Array

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

› Output: 1

💡 Note: Subarrays: [1]→1, [1,2]→3, [2]→2. Sorted: [1,2,3]. The 1st smallest is 1.

Example 3 — Negative Numbers

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

› Output: -3

💡 Note: All subarrays: [-1]→-1, [-1,2]→1, [-1,2,-3]→-2, [2]→2, [2,-3]→-1, [-3]→-3. Sorted: [-3,-2,-1,-1,1,2]. The 2nd smallest is -2.

Constraints

1 ≤ nums.length ≤ 2000
-5 × 10⁴ ≤ nums[i] ≤ 5 × 10⁴
1 ≤ k ≤ nums.length × (nums.length + 1) / 2

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array nums and target rank k

All Subarrays

Generate all contiguous subsequences and their sums

Kth Smallest

Find the kth element in sorted order

Key Takeaway

🎯 Key Insight: Binary search on answer space is more efficient than generating all sums

Asked in

G Google 35 f Facebook 28 a Amazon 22 M Microsoft 18

The key insight is to use binary search on the answer space rather than generating all sums explicitly. The binary search approach efficiently finds the kth smallest sum by counting qualifying subarrays for each candidate value. Time: O(n² log S), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Subarray Sums	O(n² log n)	O(n²)	Generate all possible subarray sums, sort them, and return the kth element
Binary Search on Answer	O(n² log S)	O(1)	Binary search on possible sum values with efficient counting

Brute Force - Generate All Subarray Sums — Algorithm Steps

Generate all subarrays using nested loops
Calculate sum for each subarray
Sort all sums in ascending order
Return the kth smallest sum

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subarrays

Find all contiguous subsequences

Calculate Sums

Sum each subarray

Sort and Select

Sort sums and pick kth element

Code -

solution.c — C

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

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int solution(int* nums, int numsSize, int k) {
    int* sums = (int*)malloc(numsSize * numsSize * sizeof(int));
    int sumCount = 0;
    
    // Generate all subarray sums
    for (int i = 0; i < numsSize; i++) {
        int currentSum = 0;
        for (int j = i; j < numsSize; j++) {
            currentSum += nums[j];
            sums[sumCount++] = currentSum;
        }
    }
    
    // Sort and return kth smallest
    qsort(sums, sumCount, sizeof(int), compare);
    int result = sums[k - 1];
    free(sums);
    return result;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n² log n)

O(n²) to generate all subarray sums, O(n² log n) to sort them

⚠ Quadratic Growth

Space Complexity

O(n²)

Store all n×(n+1)/2 subarray sums in array

⚠ Quadratic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 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

Brute Force - Generate All Subarray Sums — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler