Kth Smallest Subarray Sum — LeetCode 1918 Python Solution

The 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.

Example

Input

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

Output

3

Explanation

The subarrays of [2,1,3] are:

Python solution

class Solution:
    def kthSmallestSubarraySum(self, nums: List[int], k: int) -> int:
        def f(s):
            t = j = 0
            cnt = 0
            for i, x in enumerate(nums):
                t += x
                while t > s:
                    t -= nums[j]
                    j += 1
                cnt += i - j + 1
            return cnt >= k

        l, r = min(nums), sum(nums)
        return l + bisect_left(range(l, r + 1), True, key=f)

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1918. Kth Smallest Subarray Sum is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems