📘 Problem Statement
Given an n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Example:
python
Input: matrix = [
[1, 5, 9],
[10, 11, 13],
[12, 13, 15]
], k = 8
Output: 13
Explanation: The elements of the matrix in ascending order are [1, 5, 9, 10, 11, 12, 13, 13, 15], and the 8th smallest element is 13.
🧠 Key Insight
The matrix is sorted both row-wise and column-wise, which allows us to optimize the search for the kth smallest element using binary search. Instead of brute-forcing through all elements, we can use binary search to narrow down the potential values for the kth smallest element.
Steps:
- Binary Search Setup: We use binary search on the value of the matrix elements rather than their indices. The smallest element in the matrix is
matrix[0][0], and the largest element is matrix[n-1][n-1].
- Count Function: We need a helper function to count how many elements in the matrix are less than or equal to a given value. This count helps us decide the next search bounds.
- Binary Search: We adjust the search range based on the number of elements smaller than or equal to the midpoint of our search range. If the count is less than
k, the target value is too small, and we move the search range upwards; if it's greater than or equal to k, we move the search range downwards.
💡 Approach
- Binary Search on Value Range: The minimum value in the matrix is
matrix[0][0], and the maximum value is matrix[n-1][n-1].
- Counting Function: Given a value
mid, count how many elements in the matrix are less than or equal to mid. This can be done efficiently by iterating through each row and using a two-pointer technique or binary search within each row.
- Binary Search Loop: Perform binary search on the value range, updating the bounds based on the count.
🐍 Python Code
python
class Solution:
def kthSmallest(self, matrix: list[list[int]], k: int) -> int:
n = len(matrix)
# Function to count the number of elements less than or equal to mid
def count_less_equal(mid):
count, row, col = 0, n - 1, 0
while row >= 0 and col < n:
if matrix[row][col] <= mid:
count += row + 1 # All elements in this row up to col are <= mid
col += 1
else:
row -= 1
return count
# Binary search for the kth smallest element
left, right = matrix[0][0], matrix[n - 1][n - 1]
while left < right:
mid = (left + right) // 2
if count_less_equal(mid) < k:
left = mid + 1
else:
right = mid
return left
🔍 Step-by-Step Explanation
1. Binary Search Setup
python
left, right = matrix[0][0], matrix[n - 1][n - 1]
- We initialize the binary search range using the smallest and largest elements in the matrix, i.e., the first element (
matrix[0][0]) and the last element (matrix[n-1][n-1]).
2. Counting Function
python
def count_less_equal(mid):
count, row, col = 0, n - 1, 0
while row >= 0 and col < n:
if matrix[row][col] <= mid:
count += row + 1 # All elements in this row up to col are <= mid
col += 1
else:
row -= 1
return count
- The
count_less_equal(mid) function counts how many elements in the matrix are less than or equal to the value mid.
- We use two pointers,
row starting from the bottom-left corner (n-1, 0), and col starting from the top-left.
- If
matrix[row][col] <= mid, then all elements from matrix[row][0] to matrix[row][col] are also less than or equal to mid. We add row + 1 to the count (since there are row + 1 elements in this row that satisfy the condition) and move to the next column.
- Otherwise, we move the pointer up to check the previous row.
3. Binary Search Loop
python
while left < right:
mid = (left + right) // 2
if count_less_equal(mid) < k:
left = mid + 1
else:
right = mid
- We perform binary search on the value range
[left, right]. For each midpoint mid, we call count_less_equal(mid) to count how many elements are less than or equal to mid.
- If the count is less than
k, we know that the kth smallest element is larger than mid, so we move the left pointer up.
- If the count is greater than or equal to
k, we move the right pointer down to narrow down the search space.
4. Return the Result
python
return left
- Once the binary search loop ends, the value of
left will be the kth smallest element, which we return.
💡 Example Walkthrough
python
Input:
matrix = [
[1, 5, 9],
[10, 11, 13],
[12, 13, 15]
], k = 8
Output: 13
- The matrix is sorted row-wise and column-wise.
- The elements in ascending order are:
[1, 5, 9, 10, 11, 12, 13, 13, 15]
- The 8th smallest element is
13.
⏱️ Time & Space Complexity
MetricComplexityTime ComplexityO(n * log(max - min))Space ComplexityO(1)
- Time Complexity:
- The binary search runs in
O(log(max - min)) time, where max and min are the largest and smallest elements in the matrix.
- For each midpoint
mid, we run the count_less_equal function, which takes O(n) time (since it iterates over at most n rows and columns).
- Thus, the total time complexity is
O(n * log(max - min)).
- Space Complexity: We use constant space for the binary search and counting function, so the space complexity is
O(1).
🧵 Final Thoughts
The solution to LeetCode 378 makes good use of binary search and counting elements efficiently to narrow down the search space for the kth smallest element in a sorted matrix. This is a classic example of how binary search can be applied to optimize problems involving sorted arrays or matrices.
- Binary Search: Instead of searching the matrix linearly, binary search allows us to find the kth smallest element efficiently.
- Efficient Counting: By counting elements less than or equal to the midpoint, we can adjust our search bounds dynamically.
This approach is both time-efficient and space-efficient, making it a great choice for solving problems related to sorted matrices.