Problem 312993 · hard · Phase 03 Linear Management & Searching

Kth Smallest in a Grid Sorted Both Ways

binary search on the answer · matrices · staircase search

grid is an m x n matrix in which every row and every column is sorted in non-decreasing order. Return the k-th smallest value in the grid (duplicates count separately).

Examples

Input:  grid = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8
Output: 13

Input:  grid = [[-5]], k = 1
Output: -5

Input:  grid = [[1, 2], [1, 3]], k = 2
Output: 1

Constraints

  • 1 <= m, n <= 300, 1 <= k <= m * n
  • -10**9 <= grid[i][j] <= 10**9
  • Required time: O((m + n) log(max - min)). Flattening and sorting is too slow for the hidden tests.

Goals

  • Count grid cells <= v with a staircase walk in O(rows + cols)
  • Binary search over values that may not appear in the grid
Starting Python…