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 Technical Screen rounds at TikTok.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at TikTok during technical interviews.

Find kth smallest in sorted 2D matrix | TikTok Coding Question

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.

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

Expected Output: 15

Explanation: k = n*m = 9 returns the global maximum, matrix[2][2] = 15.

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

Expected Output: -5

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

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

Expected Output: 1

Explanation: Sorted order is [1,1,2,3]; duplicates are counted, so the 2nd smallest is the second 1.

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

Expected Output: 2

Explanation: In [1,1,2,3] the 3rd element is 2.

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

Expected Output: 11

Explanation: Sorted order is [1,3,5,6,7,11,12,14,14]; the 6th element is 11.

Input: ([[-10, -8, -8], [-7, -3, 0], [-1, 2, 5]], 5)

Expected Output: -3

Explanation: Sorted order is [-10,-8,-8,-7,-3,-1,0,2,5]; the 5th element is -3. Negatives and duplicates handled correctly.

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.

Quick Overview

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.