LeetCode Solutions Blog

Kth Smallest Subarray Sum

Number: 2069

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given an integer array nums and an integer k, find the kth smallest subarray sum. A subarray is a non-empty contiguous sequence in the array and the subarray sum is the sum of its elements.

Key Insights

All numbers in nums are positive, ensuring that subarray sums increase as more elements are added.
The range of possible subarray sums lies between the smallest element and the sum of the entire array.
Use Binary Search over this sum range to guess a candidate sum.
For each candidate, count the number of subarrays which have sums less than or equal to it using the Sliding Window (two pointers) technique.
Adjust the binary search boundaries based on the count relative to k.

Space and Time Complexity

Time Complexity: O(n log S) where n is the length of nums and S is the sum of all elements. Space Complexity: O(1) extra space (excluding the input array).

Solution

We use a binary search on the range of possible subarray sums. For each candidate sum (mid), we count how many contiguous subarrays have a sum less than or equal to mid using a sliding window approach. Because the array contains only positive integers, increasing the window always increases the sum. If the count is less than k, we know the kth smallest sum must be greater than mid; otherwise, it is less than or equal to mid. Finally, the binary search converges to the kth smallest subarray sum.

Code Solutions

# Function to find the kth smallest subarray sum in an array
def kthSmallestSubarraySum(nums, k):
    # Set the boundaries for binary search: smallest element to total sum.
    low = min(nums)  
    high = sum(nums)  
    
    # Helper function to count subarrays with a sum <= target_sum using a sliding window.
    def count_subarrays(target_sum):
        count = 0
        current_sum = 0
        left = 0
        # Iterate over the array using right pointer.
        for right in range(len(nums)):
            current_sum += nums[right]  # Add the current element to current_sum.
            # If current_sum exceeds target_sum, shrink the window from left.
            while current_sum > target_sum:
                current_sum -= nums[left]
                left += 1
            # All subarrays ending at right with start indices from left to right are valid.
            count += (right - left + 1)
        return count

    # Binary search over potential subarray sums.
    while low < high:
        mid = (low + high) // 2  # Candidate sum.
        if count_subarrays(mid) < k:
            low = mid + 1  # kth subarray sum is higher.
        else:
            high = mid  # kth subarray sum is mid or lower.
    return low

# Example usage:
# nums = [2, 1, 3]
# k = 4
# print(kthSmallestSubarraySum(nums, k))  # Output: 3