Kth Smallest Pick From Every Row
Every row of rows is sorted in non-decreasing order. Pick exactly one number from each row and add the picks up. Picks from different positions are different ways, even when the sums are equal.
Return the kth smallest sum over all the ways to pick.
Example 1
rows [[1,4],[2,3],[1,10]]
k 3
returns 7
The smallest sums are 1 + 2 + 1 = 4, then 1 + 3 + 1 = 5, then 4 + 2 + 1 = 7.
Example 2
rows [[1,2],[1,2]]
k 3
returns 3
The four ways give 2, 3, 3 and 4. The third smallest is the second 3.
Constraints
1 <= len(rows) <= 401 <= len(rows[0]) <= 40, and every row has that length1 <= rows[r][c] <= 50001 <= k <= 200, andkis at most the number of ways to pick
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Sorting and searching problems
- Most Tasks With a Few PillsHard
- Nesting BoxesHard
- Outline of the SkylineHard
- Shorten the Longest GapHard
- Two Teams of Equal SizeHard
- Height CheckerBeginner
- Kth Largest ElementBeginner
- Kth Smallest Distinct ValueBeginner