Find kth smallest in sorted 2D matrix
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an `n x m` matrix of integers where **each row and each column is sorted in non-decreasing order**.
You are also given an integer `k` such that `1 <= k <= n * m`.
Return the **k-th smallest element** in the matrix, where elements are ordered by value in non-decreasing order and duplicates are counted according to their occurrences.
**Example:**
- Input:
- `matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]]`
- `k = 8`
- All elements in sorted order: `[1, 5, 9, 10, 11, 12, 13, 13, 15]`
- Output: `13` (the 8th element in the sorted list).
Design an algorithm that is more efficient than flattening the matrix and fully sorting all `n * m` elements.
Quick Answer: This question evaluates algorithmic problem-solving and data-structure reasoning, focusing on order statistics and operations on a row- and column-sorted matrix within the Coding & Algorithms domain.
You are given an `n x m` matrix of integers where **each row and each column is sorted in non-decreasing order**.
You are also given an integer `k` such that `1 <= k <= n * m`.
Return the **k-th smallest element** in the matrix, where elements are ordered by value in non-decreasing order and duplicates are counted according to their occurrences.
**Example:**
- Input: `matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]]`, `k = 8`
- All elements in sorted order: `[1, 5, 9, 10, 11, 12, 13, 13, 15]`
- Output: `13` (the 8th element).
Design an algorithm that is more efficient than flattening the matrix and fully sorting all `n * m` elements.
Constraints
- 1 <= n, m
- Each row of matrix is sorted in non-decreasing order
- Each column of matrix is sorted in non-decreasing order
- 1 <= k <= n * m
- Elements may be negative and may contain duplicates
Examples
Input: ([[1, 5, 9], [10, 11, 13], [12, 13, 15]], 8)
Expected Output: 13
Explanation: Sorted order is [1,5,9,10,11,12,13,13,15]; the 8th element is 13 (the second 13).
Input: ([[1, 5, 9], [10, 11, 13], [12, 13, 15]], 1)
Expected Output: 1
Explanation: k=1 returns the global minimum, matrix[0][0] = 1.
Hints
- The answer is always one of the values in the matrix and lies between matrix[0][0] (smallest) and matrix[n-1][m-1] (largest). Binary search over this VALUE range instead of over positions.
- For a candidate value mid, you need count(elements <= mid). Because rows and columns are sorted, start at the bottom-left corner: if the current cell <= mid, every cell above it in this column also qualifies, so add (row + 1) and move right; otherwise move up.
- Find the smallest value v for which count(<= v) >= k. That v is the k-th smallest, and binary search converging lo==hi guarantees v is an actual matrix element.