A warehouse keeps n shelves, each holding n parcels sorted by weight, and the shelves themselves are arranged so that every column is also sorted from top to bottom. You receive this as an n x n grid weights. Return the weight of the k-th lightest parcel overall (k = 1 is the lightest). Duplicate weights count separately.
Examples
Input: weights = [[1, 4, 7], [2, 5, 8], [3, 6, 9]], k = 4
Output: 4
Explanation: in ascending order the weights are 1, 2, 3, 4, ...
Input: weights = [[2, 2], [2, 3]], k = 3
Output: 2
Constraints
1 <= n <= 300,1 <= k <= n * n- Target: O(k log n) time and O(n) extra space; do not flatten and sort the whole grid.
Goals
- Treat the rows of a grid as independent sorted streams
- Merge streams lazily with a min-heap of row heads
- Stop after exactly k pops instead of sorting everything