Kth Smallest Element in a Sorted Matrix solution and explanation
Google
9 more videos on this problem
Kth Smallest element in a matrix | Leetcode #378Techdose · 15:33 · 25K views
Kth Smallest Element in a Sorted Matrix | Leetcode 378 | Live Coding SessionCoding Decoded · 11:35 · 21K views
378. Kth Smallest Element in a Sorted Matrix | Priority Queue | Binary Search on AnswerAryan Mittal · 27:54 · 14K views
Leetcode - Kth Smallest Element in a Sorted Matrix (Python)Timothy H Chang · 5:49 · 11K views
LeetCode: Kth Smallest Element in a Sorted MatrixMike the Coder · 3:23 · 10K views
Leetcode 378. Kth Smallest Element in a Sorted Matrix [Java]if else statement · 10:59 · 9K views
Binary Search Solution on Leetcode 378: Kth Smallest Element in Sorted MatrixWinson Ye · 15:59 · 8K views
378. Kth Smallest Element in a Sorted Matrix | English | MediumSimple Code - 단순코드 · 10:34 · 2K views
Leetcode 378. Kth Smallest Element in a Sorted Matrix - Binary SearchKacy Codes · 19:33 · 2K views
Kth Smallest Element in a Sorted Matrix - LeetCode 378 - JavaScriptAlgoJS · 3:30 · 1K views
The problem
Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
You must find a solution with a memory complexity better than O(n2).
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 8th smallest number is 13
Example 2:
Input: matrix = [[-5]], k = 1 Output: -5
Constraints:
n == matrix.length == matrix[i].length1 <= n <= 300-109 <= matrix[i][j] <= 109- All the rows and columns of
matrixare guaranteed to be sorted in non-decreasing order. 1 <= k <= n2
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.
Approach overview
Problem Overview: You are given an n x n matrix where each row and column is sorted in ascending order. The task is to return the kth smallest element in the matrix. Because both rows and columns are sorted, the matrix behaves like multiple sorted lists merged together.
Approach 1: Flatten + Sort (O(n² log n²) time, O(n²) space)
The most direct solution ignores the sorted structure. Iterate through the matrix, push every element into a list, and sort it. After sorting, the element at index k - 1 is the answer. This approach is simple but inefficient because it processes all n² elements even though the matrix already provides ordering guarantees. It’s mainly useful as a baseline or quick prototype using basic array and sorting operations.
Approach 2: Min-Heap (O(k log n) time, O(n) space)
This method treats each row like a sorted list and merges them using a min-heap. Push the first element of every row into the heap along with its row and column index. Repeatedly extract the smallest element from the heap. When an element (r, c) is removed, push the next element in that row (r, c+1) if it exists. After performing k heap extractions, the last popped value is the answer. The heap size never exceeds n, making operations efficient. This technique is a classic application of heap (priority queue) for merging sorted structures.
Approach 3: Binary Search on Value Range (O(n log(max-min)) time, O(1) space)
The optimal solution performs binary search over the value range rather than indices. The smallest possible value is matrix[0][0] and the largest is matrix[n-1][n-1]. For a chosen midpoint, count how many numbers in the matrix are less than or equal to it. Because rows and columns are sorted, this count can be computed in O(n) by starting from the bottom-left corner and moving either up or right. If the count is less than k, move the search range higher; otherwise move it lower. The search converges to the kth smallest value without explicitly storing elements.
Recommended for interviews: The binary search solution is usually what interviewers expect because it leverages the sorted matrix structure and achieves O(n log(max-min)) time with constant extra space. The heap approach is also widely accepted and easier to implement. Mentioning the flatten-and-sort baseline shows understanding of the problem before optimizing.
Approach 1: Use Min-Heap
By using a min-heap (priority queue), you can efficiently extract the smallest elements one by one. Initially, insert the first element of each row into the heap. Then, repeat the process of extracting the smallest element and inserting the next element from the corresponding row. Continue this until you extract the k-th smallest element.
import heapq
def kthSmallest(matrix, k):
n = len(matrix)
min_heap = [(matrix[i][0], i, 0) for i in range(min(n, k))]
heapq.heapify(min_heap)
count, number = 0, 0
while k:
number, r, c = heapq.heappop(min_heap)
if c < n - 1:
heapq.heappush(min_heap, (matrix[r][c+1], r, c+1))
k -= 1
return number
# Example usage
print(kthSmallest([[1,5,9],[10,11,13],[12,13,15]], 8))import java.util.PriorityQueue;
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(matrix[a[0]][a[1]], matrix[b[0]][b[1]]));
for (int i = 0; i < Math.min(n, k); i++)
minHeap.offer(new int[]{i, 0});
int val = 0;
while (k-- > 0) {
int[] pos = minHeap.poll();
int r = pos[0], c = pos[1];
val = matrix[r][c];
if (c < n - 1)
minHeap.offer(new int[]{r, c + 1});
}
return val;
}
}#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
auto comp = [&](pair<int, int>& a, pair<int, int>& b) {
return matrix[a.first][a.second] > matrix[b.first][b.second];
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> minHeap(comp);
for (int r = 0; r < min(n, k); r++)
minHeap.emplace(r, 0);
int val = 0;
while (k-- > 0) {
auto [r, c] = minHeap.top();
minHeap.pop();
val = matrix[r][c];
if (c < n - 1)
minHeap.emplace(r, c + 1);
}
return val;
}
};var kthSmallest = function(matrix, k) {
let minHeap = new MinPriorityQueue({ priority: (x) => x.val });
let n = matrix.length;
for (let i = 0; i < n; i++)
minHeap.enqueue({ val: matrix[i][0], r: i, c: 0 });
let number = 0;
while (k-- > 0) {
let { val, r, c } = minHeap.dequeue().element;
number = val;
if (c < n - 1)
minHeap.enqueue({ val: matrix[r][c+1], r, c: c+1 });
}
return number;
};
console.log(kthSmallest([[1,5,9],[10,11,13],[12,13,15]], 8));#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
struct HeapNode {
int val;
int r;
int c;
};
void minHeapify(struct HeapNode heap[], int i, int heap_size) {
int smallest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < heap_size && heap[left].val < heap[smallest].val)
smallest = left;
if (right < heap_size && heap[right].val < heap[smallest].val)
smallest = right;
if (smallest != i) {
struct HeapNode temp = heap[i];
heap[i] = heap[smallest];
heap[smallest] = temp;
minHeapify(heap, smallest, heap_size);
}
}
int kthSmallest(int** matrix, int n, int k) {
struct HeapNode* heap = malloc(n * sizeof(struct HeapNode));
for (int i = 0; i < n; i++) {
heap[i].val = matrix[i][0];
heap[i].r = i;
heap[i].c = 0;
}
for (int i = n / 2 - 1; i >= 0; i--)
minHeapify(heap, i, n);
struct HeapNode hr;
for (int i = 0; i < k; i++) {
hr = heap[0];
int nextVal = (hr.c < n - 1) ? matrix[hr.r][hr.c + 1] : INT_MAX;
heap[0].val = nextVal;
heap[0].c += 1;
minHeapify(heap, 0, n);
}
int result = hr.val;
free(heap);
return result;
}
int main() {
int* matrix[3];
int a[] = {1, 5, 9};
int b[] = {10, 11, 13};
int c[] = {12, 13, 15};
matrix[0] = a;
matrix[1] = b;
matrix[2] = c;
printf("%d\n", kthSmallest(matrix, 3, 8));
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int KthSmallest(int[][] matrix, int k) {
int n = matrix.Length;
PriorityQueue<(int val, int r, int c), int> minHeap = new PriorityQueue<(int val, int r, int c), int>();
for (int i = 0; i < Math.Min(n, k); i++)
minHeap.Enqueue((matrix[i][0], i, 0), matrix[i][0]);
int number = 0;
while (k-- > 0) {
var (value, r, c) = minHeap.Dequeue();
number = value;
if (c < n - 1)
minHeap.Enqueue((matrix[r][c + 1], r, c + 1), matrix[r][c + 1]);
}
return number;
}
}This Python solution also makes use of a min-heap for tracking the smallest elements with respect to the matrix's order. By heappush and heappop operations on a zero-indexed heap, we achieve the desired order through repeated insertions of each sub-sequential next element per row. By the time k operations are performed, we arrive at the targeted smallest desired element.
Time Complexity: O(k log n), generated by heap operations across k evaluations, requiring log work proportional to row width for addition & removal.
Space Complexity: O(n) due to the heap size storing initial row heads.
Approach 2: Use Binary Search
This approach uses binary search over the range of possible values in the matrix to find the k-th smallest element. The idea is to repeatedly narrow the range by counting the number of elements in the matrix that are less than or equal to the current middle value. Depending on this count, adjust the binary search range to hone in on the k-th smallest element.
def countLessEqual(matrix, mid, n):
count, j = 0, n - 1
for i in range(n):
while j >= 0 and matrix[i][j] > mid:
j -= 1
count += j + 1
return count
def kthSmallest(matrix, k):
n = len(matrix)
left, right = matrix[0][0], matrix[n-1][n-1]
while left < right:
mid = left + (right - left) // 2
if countLessEqual(matrix, mid, n) < k:
left = mid + 1
else:
right = mid
return left
# Example usage
print(kthSmallest([[1, 5, 9], [10, 11, 13], [12, 13, 15]], 8))class Solution {
private int countLessEqual(int[][] matrix, int mid) {
int count = 0, n = matrix.length, j = n - 1;
for (int i = 0; i < n; i++) {
while (j >= 0 && matrix[i][j] > mid)
j--;
count += (j + 1);
}
return count;
}
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
int left = matrix[0][0], right = matrix[n - 1][n - 1];
while (left < right) {
int mid = left + (right - left) / 2;
if (countLessEqual(matrix, mid) < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}#include <vector>
using namespace std;
class Solution {
public:
int countLessEqual(vector<vector<int>>& matrix, int mid) {
int count = 0, n = matrix.size(), j = n - 1;
for (int i = 0; i < n; i++) {
while (j >= 0 && matrix[i][j] > mid) j--;
count += (j + 1);
}
return count;
}
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
int left = matrix[0][0], right = matrix[n-1][n-1];
while (left < right) {
int mid = left + (right - left) / 2;
int count = countLessEqual(matrix, mid);
if (count < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
};function countLessEqual(matrix, mid, n) {
let count = 0;
let j = n - 1;
for (let i = 0; i < n; i++) {
while (j >= 0 && matrix[i][j] > mid) {
j--;
}
count += (j + 1);
}
return count;
}
function kthSmallest(matrix, k) {
const n = matrix.length;
let left = matrix[0][0], right = matrix[n - 1][n - 1];
while (left < right) {
let mid = left + ((right - left) >> 1);
if (countLessEqual(matrix, mid, n) < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
console.log(kthSmallest([[1, 5, 9], [10, 11, 13], [12, 13, 15]], 8));#include <stdio.h>
int countLessEqual(int** matrix, int n, int mid) {
int count = 0;
int col = n - 1;
for (int row = 0; row < n; row++) {
while (col >= 0 && matrix[row][col] > mid) {
col--;
}
count += (col + 1);
}
return count;
}
int kthSmallest(int** matrix, int n, int k) {
int start = matrix[0][0], end = matrix[n-1][n-1];
while (start < end) {
int mid = start + (end - start) / 2;
int count = countLessEqual(matrix, n, mid);
if (count < k) {
start = mid + 1;
} else {
end = mid;
}
}
return start;
}
int main() {
int* matrix[3];
int a[] = {1, 5, 9};
int b[] = {10, 11, 13};
int c[] = {12, 13, 15};
matrix[0] = a;
matrix[1] = b;
matrix[2] = c;
printf("%d\n", kthSmallest(matrix, 3, 8));
return 0;
}public class Solution {
private int CountLessEqual(int[,] matrix, int mid) {
int count = 0, n = matrix.GetLength(0), col = n - 1;
for (int row = 0; row < n; row++) {
while (col >= 0 && matrix[row, col] > mid) col--;
count += (col + 1);
}
return count;
}
public int KthSmallest(int[,] matrix, int k) {
int n = matrix.GetLength(0);
int left = matrix[0, 0], right = matrix[n - 1, n - 1];
while (left < right) {
int mid = left + (right - left) / 2;
if (CountLessEqual(matrix, mid) < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}This Python solution incorporates a binary search active over value dimensions between smallest and greatest items in—effecting columnar row traversals. It coarsely pinpoints upsurge breaks when element critiques lag below a desired cast, abiding till conclusive restraint among possible k-th outcomes arises.
Time Complexity: O(n log(max-min)), determined due to combined matrix cross-seam examination inside count-regulated loops with logarithmic value steps.
Space Complexity: O(1), reflecting pure iterative control without memorization beyond existential data calculus directly attached to the matrix itself.
Approach 3: Default Approach
func kthSmallest(matrix [][]int, k int) int {
n := len(matrix)
left, right := matrix[0][0], matrix[n-1][n-1]
for left < right {
mid := (left + right) >> 1
if check(matrix, mid, k, n) {
right = mid
} else {
left = mid + 1
}
}
return left
}
func check(matrix [][]int, mid, k, n int) bool {
count := 0
i, j := n-1, 0
for i >= 0 && j < n {
if matrix[i][j] <= mid {
count += (i + 1)
j++
} else {
i--
}
}
return count >= k
}Complexity comparison
| Approach | Complexity |
|---|---|
| Use Min-Heap | Time Complexity: |
| Use Binary Search | Time Complexity: |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Flatten Matrix + Sort | O(n² log n²) | O(n²) | Simple baseline when constraints are small or quick implementation is needed |
| Min-Heap (Merge Sorted Rows) | O(k log n) | O(n) | Good when k is small relative to n² and you want a straightforward heap solution |
| Binary Search on Value Range | O(n log(max-min)) | O(1) | Best for interviews and large matrices since it uses the sorted row/column property efficiently |
Frequently asked questions
Is Kth Smallest Element in a Sorted Matrix easy or hard?
The problem is usually classified as Medium difficulty. A straightforward heap implementation is manageable once you recognize the matrix behaves like multiple sorted lists. The binary search optimization requires deeper insight into searching the value space and leveraging row and column ordering.
Kth Smallest Element in a Sorted Matrix Python or Java solution?
Python and Java solutions typically implement either a PriorityQueue/min-heap or binary search. The heap version pushes the first element of each row and repeatedly pops the smallest until k elements are removed. The binary search version checks how many values are <= mid using a linear scan from the bottom-left corner.
What is the best approach for Kth Smallest Element in a Sorted Matrix?
Binary search on the value range is generally considered the best approach. It searches between the smallest and largest matrix values and counts how many elements are <= mid using the sorted row and column property. This runs in O(n log(max-min)) time and O(1) extra space. A min-heap approach with O(k log n) time is also commonly accepted in interviews.
How to solve Kth Smallest Element in a Sorted Matrix in O(n log range)?
Perform binary search between matrix[0][0] and matrix[n-1][n-1]. For each midpoint, count how many elements in the matrix are less than or equal to it by scanning from the bottom-left corner and moving up or right. If the count is smaller than k, shift the search range higher; otherwise move it lower. The final boundary value becomes the kth smallest element.
Is Kth Smallest Element in a Sorted Matrix asked at Google/Amazon/Meta?
Kth Smallest Element in a Sorted Matrix is a common interview problem at large tech companies including Google, Amazon, and Meta. It tests understanding of binary search on answer space, heap usage, and exploiting sorted matrix properties. Variants of the problem appear in coding interviews and competitive programming.
What data structure is used in Kth Smallest Element in a Sorted Matrix?
Two main techniques appear in solutions. A min-heap (priority queue) is used to merge sorted rows similarly to merging k sorted lists. The optimal solution relies on binary search over the value range combined with matrix traversal, which avoids storing extra elements.
What is the time complexity of Kth Smallest Element in a Sorted Matrix?
The optimal binary search solution runs in O(n log(max-min)) time where n is the matrix dimension and max-min is the numeric range of values. Each binary search step counts elements <= mid in O(n) time. The heap-based method runs in O(k log n) time with O(n) space.