Leetcode Problem 378. Kth Smallest Element in a Sorted Matrix

378. Kth Smallest Element in a Sorted Matrix

Leetcode Solutions

Binary Search Approach

  1. Initialize start to matrix[0][0] and end to matrix[n-1][n-1], where n is the number of rows/columns in the matrix.
  2. While start is less than end: a. Calculate mid as the average of start and end. b. Initialize count to 0 and max_of_smaller to start. c. For each row in the matrix, use a pointer to count how many numbers are less than or equal to mid. Update max_of_smaller to the largest of these numbers. d. If count is equal to k, return max_of_smaller. e. If count is less than k, set start to max_of_smaller + 1. Otherwise, set end to max_of_smaller.
  3. Return start as the kth smallest element.
UML Thumbnail

Min-Heap Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...