How do you solve Kth Smallest Element in a Sorted Matrix on LeetCode?

Kth Smallest Element in a Sorted Matrix (LeetCode #378) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log(max-min)) time complexity and O(1) space complexity. Key insight: The matrix is sorted both row-wise and column-wise, allowing for efficient searching.

What is the brute force solution for Kth Smallest Element in a Sorted Matrix?

The brute force approach for Kth Smallest Element in a Sorted Matrix is Brute Force, with O(n² log(n)) time complexity and O(n²) space complexity. The brute force approach involves flattening the matrix into a single list and then sorting that list. This allows us to easily access the k-th smallest element. However, this method is inefficient due to the extra space required and the sorting step. The optimal Optimal Solution approach improves this to O(n log(max-min)).

What are the interview tips for Kth Smallest Element in a Sorted Matrix?

Always clarify whether duplicates count towards k-th smallest or distinct. Discuss the time and space complexities of your approach before coding. If using binary search, explain how you will count elements efficiently.

What are common mistakes when solving Kth Smallest Element in a Sorted Matrix?

Confusing the k-th smallest element with the k-th distinct element. Not considering the sorted properties of the matrix when implementing the brute force approach.

#378

Kth Smallest Element in a Sorted Matrix

Medium

ArrayBinary SearchSortingHeap (Priority Queue)MatrixBinary SearchMatrix Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n² log(n))	O(n log(max-min))
Space	O(n²)	O(1)

💡

Intuition

Time O(n log(max-min))Space O(1)

The optimal solution uses a binary search approach on the value range of the matrix elements. By counting how many elements are less than or equal to a mid value, we can narrow down the search space efficiently.

⚙️

Algorithm

5 steps

1Step 1: Initialize low as the smallest element and high as the largest element in the matrix.
2Step 2: Perform binary search until low is less than high.
3Step 3: For each mid value, count how many elements are less than or equal to mid.
4Step 4: If the count is less than k, move low to mid + 1; otherwise, move high to mid.
5Step 5: When low equals high, return low as the k-th smallest element.

solution.py11 lines

1def kthSmallest(matrix, k):
2    n = len(matrix)
3    low, high = matrix[0][0], matrix[n-1][n-1]
4    while low < high:
5        mid = (low + high) // 2
6        count = sum(bisect.bisect_right(row, mid) for row in matrix)
7        if count < k:
8            low = mid + 1
9        else:
10            high = mid
11    return low

ℹ

Complexity note: The time complexity is O(n log(max-min)) where max and min are the largest and smallest elements in the matrix, respectively. The space complexity is O(1) as we are not using any extra space proportional to the input size.

1The matrix is sorted both row-wise and column-wise, allowing for efficient searching.
2Using binary search on the value range instead of the indices allows us to avoid sorting the entire matrix.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.