975. Kth Cheapest Row Picks
A catering plan has one menu per course. Row i of grid lists the prices of the dishes for course i, already sorted in non-decreasing order. A meal picks exactly one dish from every course, and its cost is the sum of the picked prices.
Two meals are different if they pick a different column in at least one row, even when the costs are equal. List the costs of all meals in non-decreasing order and return the k-th one (1-indexed).
Example 1
- Input:
- grid = [[1,4,9],[2,3,7]], k = 4
- Output:
- 7
- Explanation:
The nine sums in order are 3, 4, 6, 7, 8, 11, 11, 12, 16, and the fourth one is 7 (4 + 3).
Example 2
- Input:
- grid = [[5],[6],[7]], k = 1
- Output:
- 18
- Explanation:
Each row has a single choice, so the only (and cheapest) pick sums to 18.
Example 3
- Input:
- grid = [[1,1],[1,1]], k = 3
- Output:
- 2
- Explanation:
All four picks cost 2; picks that use different columns count separately, so the third cheapest is 2.
Constraints
- 1 ≤ grid.length, grid[i].length ≤ 40
- 1 ≤ grid[i][j] ≤ 104 and every row is sorted non-decreasing
- 1 ≤ k ≤ min(200, product of the row lengths)
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 600 msC++ 150 msJava 300 msJavaScript 300 msTypeScript 300 ms
Expected complexity
- Time
- O(m * k * log k)
- Space
- O(k)