Kth Smallest Subarray Sum
01 · Problem
You are given an array nums of positive integers with length n, and an integer k.
Consider every non-empty contiguous subarray of nums and compute its sum. There are exactly n * (n + 1) / 2 such subarrays. Sort all of these sums in non-decreasing order (keeping duplicates) and return the k-th value in that order (1-indexed).
k is always valid: 1 <= k <= n * (n + 1) / 2.
02 · Examples
nums = [2,1,3], k = 4
3
The subarray sums are [2]=2, [1]=1, [3]=3, [2,1]=3, [1,3]=4, [2,1,3]=6. Sorted: 1, 2, 3, 3, 4, 6. The 4th smallest is 3.
nums = [3,3,5,5], k = 7
10
The ten subarray sums sorted are 3, 3, 5, 5, 6, 8, 10, 11, 13, 16. The 7th smallest is 10.
nums = [4], k = 1
4
There is only one subarray, [4], with sum 4.
03 · Constraints
- 011 <= nums.length <= 2 * 104
- 021 <= nums[i] <= 5 * 104
- 031 <= k <= nums.length * (nums.length + 1) / 2
04 · Optimal complexity
- Time
- O(n log(sum(nums)))
- Space
- O(1)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.