Kth Smallest Element in a Sorted Matrix

MEDIUM

Description

Given an n x n matrix where each of the rows and columns is sorted in ascending order, 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.

You must find a solution with a memory complexity better than O(n²).

Example 1:

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8^th smallest number is 13

Example 2:

Input: matrix = [[-5]], k = 1
Output: -5

Constraints:

n == matrix.length == matrix[i].length
1 <= n <= 300
-10⁹ <= matrix[i][j] <= 10⁹
All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
1 <= k <= n²

Follow up:

Could you solve the problem with a constant memory (i.e., O(1) memory complexity)?
Could you solve the problem in O(n) time complexity? The solution may be too advanced for an interview but you may find reading this paper fun.

Approaches

Checkout 3 different approaches to solve Kth Smallest Element in a Sorted Matrix. Click on different approaches to view the approach and algorithm in detail.

Brute Force: Flatten and Sort

A straightforward approach is to treat the matrix as a simple list of numbers. We can iterate through the entire matrix, add all its elements into a single list, and then sort this list. The k-th smallest element will then be the element at the (k-1)-th index of the sorted list.

Algorithm

Initialize an empty list, say flatList. - Iterate through each row of the n x n matrix. - For each row, iterate through its elements and add them to flatList. - After iterating through all elements, the flatList will contain all n^2 elements from the matrix. - Sort flatList in ascending order. - Return the element at index k - 1.

This method ignores the sorted property of the rows and columns during the search, only using it implicitly by the fact that sorting will find the k-th element. The steps are as follows: First, we create a one-dimensional list. Then, we traverse the 2D matrix row by row, and for each element, we add it to our list. This process effectively flattens the matrix into a list of size n*n. Finally, we use a standard sorting algorithm to sort the list and pick the element at index k-1. java import java.util.ArrayList; import java.util.Collections; import java.util.List; class Solution { public int kthSmallest(int[][] matrix, int k) { int n = matrix.length; List<Integer> flatList = new ArrayList<>(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { flatList.add(matrix[i][j]); } } Collections.sort(flatList); return flatList.get(k - 1); } }

Complexity Analysis

Time Complexity: O(n^2 * log(n)) - It takes O(n^2) to iterate through the matrix and create the flat list. Sorting a list of n^2 elements takes O(n^2 * log(n^2)), which simplifies to O(n^2 * log(n)).Space Complexity: O(n^2) - We need to create a new list to store all n^2 elements from the matrix.

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

Highly inefficient in both time and space.
The space complexity of O(n^2) violates the problem's memory constraints.

Code Solutions

Checking out 3 solutions in different languages for Kth Smallest Element in a Sorted Matrix. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Kth Smallest Element in a Sorted Matrix

Algorithms:

Binary SearchSorting

Data Structures:

ArrayHeap (Priority Queue)Matrix

Companies:

Salesforce |PhonePe |X |OKX |