Skip to main content
Talentd

Kth Smallest Subarray Sum - Solution & Explanation

MediumPremiumFree on FleetCodeArrayBinary SearchSliding Window18 min readAsked at: Google
Practice this problem

Problem Statement

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.

 

Example 1:

Input: nums = [2,1,3], k = 4
Output: 3
Explanation: The subarrays of [2,1,3] are:
- [2] with sum 2
- [1] with sum 1
- [3] with sum 3
- [2,1] with sum 3
- [1,3] with sum 4
- [2,1,3] with sum 6 
Ordering the sums from smallest to largest gives 1, 2, 3, 3, 4, 6. The 4th smallest is 3.

Example 2:

Input: nums = [3,3,5,5], k = 7
Output: 10
Explanation: The subarrays of [3,3,5,5] are:
- [3] with sum 3
- [3] with sum 3
- [5] with sum 5
- [5] with sum 5
- [3,3] with sum 6
- [3,5] with sum 8
- [5,5] with sum 10
- [3,3,5], with sum 11
- [3,5,5] with sum 13
- [3,3,5,5] with sum 16
Ordering the sums from smallest to largest gives 3, 3, 5, 5, 6, 8, 10, 11, 13, 16. The 7th smallest is 10.

 

Constraints:

  • n == nums.length
  • 1 <= n <= 2 * 104
  • 1 <= nums[i] <= 5 * 104
  • 1 <= k <= n * (n + 1) / 2

Approach Overview

Problem Overview: Given an array of positive integers, return the kth smallest sum among all possible contiguous subarrays. Instead of listing every subarray explicitly, the goal is to determine the rank of subarray sums efficiently.

Approach 1: Brute Force Enumeration (O(n² log n) time, O(n²) space)

Generate every possible subarray and compute its sum. You iterate over all start indices and extend the subarray to the right while maintaining a running sum. Store each sum in a list, then sort the list and return the element at index k-1. This approach is easy to implement and demonstrates the full search space of arrays, but it becomes impractical for large n because the number of subarrays grows to n(n+1)/2.

Approach 2: Prefix Sum + Min Heap (O(n log n + k log n) time, O(n) space)

Precompute prefix sums so any subarray sum can be calculated quickly. Treat each starting index as a sorted list of possible subarray sums and push the smallest candidate for each start into a min heap. Repeatedly pop the smallest sum and push the next subarray extension for that start index. This technique is similar to merging sorted lists and allows you to extract the kth smallest sum without generating all possibilities. The heap keeps the smallest candidates available at each step.

Approach 3: Binary Search + Sliding Window (O(n log S) time, O(1) space)

The optimal approach avoids generating subarrays entirely. Instead, binary search the answer over the possible sum range [min(nums), sum(nums)]. For a candidate sum mid, count how many subarrays have sum ≤ mid. Because all numbers are positive, a sliding window works: expand the right pointer while maintaining a running sum, and shrink the left pointer when the sum exceeds mid. Every valid window contributes right - left + 1 subarrays ending at right. This counting step runs in O(n). Combine it with binary search over the sum space to locate the smallest value whose count is at least k.

Recommended for interviews: Binary Search + Sliding Window. Interviewers expect you to recognize that the answer space can be searched instead of enumerating subarrays. The sliding window counting trick converts a potentially quadratic enumeration into a linear check, producing an overall O(n log S) solution. Mentioning the brute force first shows understanding of the problem space, but implementing the binary search approach demonstrates stronger algorithmic intuition.

Solution

We observe that all elements in the array are positive integers. The larger the subarray sum s, the more subarrays there are with sums less than or equal to s. This monotonicity allows us to use binary search to solve the problem.

We perform binary search on the subarray sum, initializing the left and right boundaries as the minimum value in the array nums and the sum of all elements in the array, respectively. Each time, we calculate the number of subarrays with sums less than or equal to the current middle value. If the count is greater than or equal to k, it means the current middle value s might be the k-th smallest subarray sum, so we shrink the right boundary. Otherwise, we increase the left boundary. After the binary search ends, the left boundary will be the k-th smallest subarray sum.

The problem reduces to calculating the number of subarrays in an array with sums less than or equal to s, which we can compute using a function f(s).

The function f(s) is calculated as follows:

  • Initialize two pointers j and i, representing the left and right boundaries of the current window, with j = i = 0. Also, initialize the sum of elements in the window t = 0.
  • Use a variable cnt to record the number of subarrays with sums less than or equal to s, initially cnt = 0.
  • Traverse the array nums. For each element nums[i], add it to the window, i.e., t = t + nums[i]. If t > s, move the left boundary of the window to the right until t leq s, i.e., repeatedly execute t -= nums[j] and j = j + 1. Then update cnt as cnt = cnt + i - j + 1. Continue to the next element until the entire array is traversed.

Finally, return cnt as the result of the function f(s).

Time complexity is O(n times log S), where n is the length of the array nums, and S is the sum of all elements in the array nums. Space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustScala

Python

Java

C++

Go

TypeScript

Rust

Scala

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n² log n)O(n²)Small arrays or when demonstrating the baseline approach
Prefix Sum + Min HeapO(n log n + k log n)O(n)Useful when extracting the first k smallest sums without scanning all subarrays
Binary Search + Sliding WindowO(n log S)O(1)Best general solution when the array contains positive integers

Video Solution

1918 Kth Smallest Subarray Sum (binary search + sliding window) • LetsCode • 825 views views

Watch 2 more video solutions →

Frequently Asked Questions

Is Kth Smallest Subarray Sum easy or hard?
This problem is generally classified as Medium. The challenge is recognizing that you should binary search the sum space instead of generating all subarrays, and then using a sliding window to count valid sums efficiently.
How to solve Kth Smallest Subarray Sum in O(n log S)?
Binary search the target sum between the minimum element and the total array sum. For each mid value, use a sliding window to count how many subarrays have sum ≤ mid. If the count is at least k, move the search left; otherwise move right. The smallest value that satisfies the condition is the kth smallest subarray sum.
What is the best approach for Kth Smallest Subarray Sum?
Binary Search combined with a Sliding Window is the most efficient approach. You binary search the possible sum range and count how many subarrays have sum less than or equal to the candidate value using two pointers. Each check runs in O(n), producing an overall complexity of O(n log S), where S is the total array sum.
What data structure is used in Kth Smallest Subarray Sum?
The optimal solution primarily relies on two pointers (sliding window) and binary search over the answer range. Alternative solutions may use prefix sums and a min heap to extract the smallest subarray sums incrementally.
What is the time complexity of Kth Smallest Subarray Sum?
The optimal solution runs in O(n log S) time and O(1) extra space. The log S factor comes from binary searching the answer space of possible subarray sums, while the sliding window counts valid subarrays in linear time for each candidate.
Kth Smallest Subarray Sum Python or Java solution approach
Python and Java implementations typically follow the Binary Search + Sliding Window pattern. Maintain two pointers and a running sum to count subarrays ≤ mid, then adjust the binary search bounds until the kth smallest sum is found.
Is Kth Smallest Subarray Sum asked at Google, Amazon, or Meta?
Variants of this problem appear in interviews at companies like Amazon, Google, and Meta because it combines binary search on answer space with two‑pointer techniques. Interviewers use it to evaluate understanding of sliding window patterns and counting strategies.

Ready to solve this problem?

Practice Kth Smallest Subarray Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays