K-th Smallest Stretch Sum

Medium

You get an array of positive integers values and a number rank. A *stretch* is a non-empty contiguous part of the array; an array of length n has exactly n·(n+1)/2 of them. Take the sum of each stretch, list all the sums in ascending order (equal sums listed separately) and return the one in position rank (counting from 1). Listing every sum is O(n²); try to do better.

Example 1

values=[4, 1, 2], rank=3 → 3

The sums of all stretches are 4, 1, 2, 4 + 1 = 5, 1 + 2 = 3 and 4 + 1 + 2 = 7. Sorted: 1, 2, 3, 4, 5, 7, so the third is 3.

Example 2

values=[2, 2, 2], rank=5 → 4

The sums are 2 three times, 4 twice and 6 once. Position five holds 4: equal sums count separately.

Constraints

1 ≤ len(values) = n ≤ 2 · 10⁴
1 ≤ values[i] ≤ 5 · 10⁴
1 ≤ rank ≤ n·(n+1)/2

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search Sliding Window

Similar problems

Shortest Stretch to the Goal Medium Nearest k Values Medium Windows With a Small Product Medium Longest Shared Run Medium Longest Run of Ones With k Fixes Medium

Input

values=[4, 1, 2], rank=3

Expected

Run checks the first 3 tests in your browser. Submit checks all 69 tests on the server, hidden ones included.