LeetCode 1918 - Kth Smallest Subarray Sum

The problem asks us to find the kth smallest sum among all possible non-empty contiguous subarrays of a given integer array nums. Each subarray is formed by taking a contiguous sequence of elements from nums, and its sum is the sum of the elements in that subarray.

leetcodemediumarraybinary-searchsliding-window

LeetCode Problem 1918

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Sliding Window

Solution

Problem Understanding

The problem asks us to find the kth smallest sum among all possible non-empty contiguous subarrays of a given integer array nums. Each subarray is formed by taking a contiguous sequence of elements from nums, and its sum is the sum of the elements in that subarray. The input consists of the array nums and an integer k, and the output should be a single integer representing the kth smallest subarray sum when all subarray sums are ordered from smallest to largest.

For example, in nums = [2,1,3], the subarrays are [2], [1], [3], [2,1], [1,3], and [2,1,3], giving sums [2,1,3,3,4,6]. The 4th smallest sum is 3.

Constraints provide important insights into the problem scale. The array can be up to 2 * 10^4 elements long, and the elements themselves can be up to 5 * 10^4. The number of possible subarrays is n*(n+1)/2, which could be up to roughly 200 million for maximum n. This rules out any solution that explicitly generates all subarray sums. The constraints also guarantee that k is valid, i.e., 1 <= k <= n*(n+1)/2.

Important edge cases include arrays of length 1, arrays with repeated values, k = 1 (smallest sum), and k = n*(n+1)/2 (largest sum). A naive solution that generates all sums will fail due to both time and memory constraints.

Approaches

The brute-force approach involves generating every subarray and computing its sum, then sorting the list of sums and returning the kth smallest. While this is conceptually simple and correct, it is computationally infeasible for large arrays because the number of subarrays grows quadratically, and sorting them adds further overhead.

The key observation for an optimal solution is that subarray sums are continuous sums of elements, and all individual sums are positive due to nums[i] >= 1. This allows the use of binary search on the possible sum values in combination with a sliding window/counting technique to determine how many subarray sums are less than or equal to a candidate sum. This approach avoids explicitly storing all subarray sums.

We can define a helper function that, given a target sum mid, counts the number of subarrays with sum less than or equal to mid using a two-pointer technique. Then, using binary search over the sum range [min(nums), sum(nums)], we find the smallest sum for which there are at least k subarrays smaller than or equal to it.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2 log n) O(n^2) Generate all subarray sums, sort, and pick kth
Optimal (Binary Search + Sliding Window) O(n log(Sum_max)) O(1) Binary search on possible sum values with two-pointer counting

Algorithm Walkthrough

  1. Initialize the search range: Set left to the minimum element in nums (smallest possible subarray sum) and right to the sum of all elements (largest possible subarray sum).
  2. Binary search loop: While left < right, compute mid = (left + right) // 2.
  3. Count subarrays <= mid: Use a two-pointer sliding window. Start with start = 0 and curr_sum = 0. Iterate end over all elements of nums, adding nums[end] to curr_sum. While curr_sum > mid, subtract nums[start] and increment start. At each step, the number of subarrays ending at end and ≤ mid is end - start + 1. Accumulate this count.
  4. Adjust binary search bounds: If the count is less than k, we need larger sums, so set left = mid + 1. Otherwise, set right = mid.
  5. Return result: When left == right, it represents the kth smallest subarray sum.

Why it works: The algorithm leverages the monotonic relationship between subarray sums and the binary search. Counting subarrays ≤ mid ensures that the binary search correctly identifies the smallest sum where at least k subarrays exist below it.

Python Solution

from typing import List

class Solution:
    def kthSmallestSubarraySum(self, nums: List[int], k: int) -> int:
        def count_subarrays_le(target: int) -> int:
            count = 0
            curr_sum = 0
            start = 0
            for end, val in enumerate(nums):
                curr_sum += val
                while curr_sum > target:
                    curr_sum -= nums[start]
                    start += 1
                count += end - start + 1
            return count

        left, right = min(nums), sum(nums)
        while left < right:
            mid = (left + right) // 2
            if count_subarrays_le(mid) < k:
                left = mid + 1
            else:
                right = mid
        return left

Implementation Explanation: The count_subarrays_le helper uses a sliding window to efficiently count subarrays with sums ≤ target. Binary search is applied to find the minimum sum for which the count is at least k. This ensures we efficiently find the kth smallest sum without enumerating all subarrays.

Go Solution

func kthSmallestSubarraySum(nums []int, k int) int {
    countSubarraysLE := func(target int) int {
        count, currSum, start := 0, 0, 0
        for end, val := range nums {
            currSum += val
            for currSum > target {
                currSum -= nums[start]
                start++
            }
            count += end - start + 1
        }
        return count
    }

    left, right := nums[0], 0
    for _, val := range nums {
        if val < left {
            left = val
        }
        right += val
    }

    for left < right {
        mid := (left + right) / 2
        if countSubarraysLE(mid) < k {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

Go Notes: The Go version mirrors the Python implementation closely. The helper is an inline function. Care is taken with integer division and sum accumulation. Go slices handle empty or singleton arrays naturally.

Worked Examples

Example 1: nums = [2,1,3], k = 4

Step left right mid count_subarrays_le(mid) Action
1 1 6 3 4 right = 3
2 1 3 2 2 left = 3
Done left = 3 right = 3 Return 3

Example 2: nums = [3,3,5,5], k = 7

Step left right mid count_subarrays_le(mid) Action
1 3 16 9 5 left = 10
2 10 16 13 8 right = 13
3 10 13 11 7 right = 11
4 10 11 10 6 left = 11
Done left = 10 right = 10 Return 10

Complexity Analysis

Measure Complexity Explanation
Time O(n log(S)) Binary search over sum range S = sum(nums), each counting in O(n)
Space O(1) Only variables and counters are used; no additional arrays

Even though sum(nums) can be large (up to 10^9 for max constraints), log(S) is small (~30), making this efficient for n <= 2*10^4.

Test Cases

# Provided examples
assert Solution().kthSmallestSubarraySum([2,1,3], 4) == 3  # Example 1
assert Solution().kthSmallestSubarraySum([3,3,5,5], 7) == 10  # Example 2

# Edge cases
assert Solution().kthSmallestSubarraySum([1], 1) == 1  # Single element
assert Solution().kthSmallestSubarraySum([1,2,3], 1) == 1  # Smallest sum
assert Solution().kthSmallestSubarraySum([1,2,3], 6) == 6  # Largest sum
assert Solution().kthSmallestSubarraySum([1,1,