Katkat
Back

Find kth smallest in sorted 2D matrix

TikTokSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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 in the sorted list).

Design an algorithm that is more efficient than flattening the matrix and fully sorting all n * m elements.