How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Meta.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Meta during technical interviews.

Find kth smallest in sorted matrix | Meta Coding Question

Quick Overview

This question evaluates algorithmic problem-solving and data-structure knowledge, focusing on selection in a row-and-column-sorted matrix and the comparative use of min-heaps versus value-space binary search along with time/space complexity and edge-case analysis.

Find kth smallest in sorted matrix

Company: Meta

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given an n x n matrix where each row and each column is sorted in nondecreasing order, and an integer k (1 ≤ k ≤ n^ 2), return the k-th smallest element in the matrix. Compare approaches using a min-heap over row heads versus value-space binary search with counting, and analyze complexities and edge cases.

Quick Answer: This question evaluates algorithmic problem-solving and data-structure knowledge, focusing on selection in a row-and-column-sorted matrix and the comparative use of min-heaps versus value-space binary search along with time/space complexity and edge-case analysis.

Given an n x n matrix where each row and each column is sorted in non-decreasing order, and an integer k (1 ≤ k ≤ n^2), return the k-th smallest element in the matrix. Note that it is the k-th smallest element in the sorted order, not the k-th distinct element. Duplicate values count toward k. A min-heap over the row heads gives an O(k log n) solution: seed the heap with the first element of every row, then pop k times, each time pushing the next element from the same row. An alternative value-space binary search with a counting routine runs in O(n log(max-min)) and counts, for a candidate value x, how many matrix entries are ≤ x by walking from the bottom-left corner. Example: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 → 13 (sorted order: 1,5,9,10,11,12,13,13,15; the 8th element is 13).

Constraints

n == matrix.length == matrix[i].length
1 <= n <= 300
Each row and each column of matrix is sorted in non-decreasing order
1 <= k <= n^2
-10^9 <= matrix[i][j] <= 10^9

Examples

Input: ([[1,5,9],[10,11,13],[12,13,15]], 8)

Expected Output: 13

Explanation: Sorted order: 1,5,9,10,11,12,13,13,15. The 8th smallest is 13 (the second 13).

Input: ([[1,2],[1,3]], 2)

Expected Output: 1

Explanation: Sorted order: 1,1,2,3. Duplicates count, so the 2nd smallest is the second 1.

Input: ([[-5]], 1)

Expected Output: -5

Explanation: Single-cell matrix; the only element is the 1st smallest.

Input: ([[1,5,9],[10,11,13],[12,13,15]], 1)

Expected Output: 1

Explanation: k=1 boundary: the smallest element is the top-left corner.

Input: ([[1,5,9],[10,11,13],[12,13,15]], 9)

Expected Output: 15

Explanation: k=n^2 boundary: the largest element is the bottom-right corner.

Input: ([[1,3,5],[6,7,12],[11,14,14]], 6)

Expected Output: 11

Explanation: Sorted order: 1,3,5,6,7,11,12,14,14. The 6th smallest is 11.

Input: ([[1,2],[3,3]], 4)

Expected Output: 3

Explanation: Sorted order: 1,2,3,3. The 4th (last) smallest is 3.

Hints

The whole matrix isn't globally sorted, but each row IS sorted. Think of merging n sorted lists (the rows) and stopping after k elements.
Use a min-heap seeded with the head of each row: (value, rowIndex, colIndex). Pop the smallest, then push the next element from that same row.
After k pops, the last popped value is the answer. Each value pushed/popped costs O(log n).
Alternative: binary search on the value range [matrix[0][0], matrix[n-1][n-1]]. For a candidate x, count how many entries are <= x by walking from the bottom-left corner in O(n); shrink the range until you isolate the k-th smallest.

Quick Overview