Find k-th smallest subarray sum

Problem

You are given an integer array nums of length n where all elements are positive integers, and an integer k.

Consider all non-empty contiguous subarrays of nums. Each subarray has a sum.

Return the k-th smallest subarray sum (1-indexed) among all subarrays.

Input

• nums : array of positive integers
• k : integer (1-indexed rank)

Output

• An integer: the k-th smallest subarray sum

Constraints

• 1 <= n <= 2 * 10^4
• 1 <= nums[i] <= 10^4
• 1 <= k <= n * (n + 1) / 2

Example

• nums = [2, 1, 3] , k = 4
  • Subarray sums: [2, 3, 6, 1, 4, 3]
  • Sorted: [1, 2, 3, 3, 4, 6]
  • 4th smallest is 3
  • Output: 3

Notes

• Because n can be large, an O(n^2) approach that enumerates all subarrays is too slow.