A LeetCode Daily Series — Day 91

Today’s problem is called "Kth Smallest Element in a Sorted Matrix"

Updated: at 06:09 AM

In this article, we will delve into the fascinating problem of finding the kth smallest element in a sorted matrix. This problem is not only interesting but also offers a great opportunity to explore different algorithmic approaches, including brute force and binary search. Let’s dive in!

If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!

Cover Image

Understanding the Problem

Given an 𝑛×𝑛 matrix where each of the rows and columns is sorted in ascending order, we need to find the kth smallest element in the matrix. It is important to note that the matrix is sorted in non-decreasing order both row-wise and column-wise. We aim to solve this problem with a memory complexity better than 𝑂(𝑛^2).

Example 1:

Input: s = "(abcd)"
Output: "dcba"

Example 2:

Input: s = "(u(love)i)"
Output: "iloveu"
Explanation: The substring "love" is reversed first, then the whole string is reversed.

Example 3:

Input: s = "(ed(et(oc))el)"
Output: "leetcode"
Explanation: First, we reverse the substring "oc", then "etco", and finally, the whole string.

Brute Force Approach

The brute force approach involves flattening the entire matrix into a single list, sorting that list, and then returning the kth smallest element. While this method is straightforward and easy to implement, it is not efficient for large matrices due to its high time and space complexity.

def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
    mat = []
    for row in matrix:
        mat.extend(row)

    mat.sort()
    return mat[k - 1]

Explanation

  1. Flatten the Matrix:
    • We create an empty list mat.
    • We iterate through each row of the matrix and extend the mat list with the elements of each row, effectively flattening the matrix.
  2. Sort the List:
    • We sort the flattened list mat.
  3. Return the kth Smallest Element:
    • We return the element at the 𝑘−1 index of the sorted list mat, as list indices are zero-based.

Time Complexity: 𝑂(𝑛^2×log𝑛), Flattening the matrix takes 𝑂(𝑛^2) time. Sorting the flattened list takes 𝑂(𝑛^2×log𝑛) time.

Space Complexity: 𝑂(𝑛^2), We use an additional list to store the flattened matrix, which requires 𝑂(𝑛^2) space.

Brute Force Result

Thinking More Efficiently

To solve this problem more efficiently, we can leverage the properties of the sorted matrix and use a binary search approach. This allows us to significantly reduce the search space and achieve better time complexity.

The binary search approach is based on the observation that the elements in the matrix are sorted. We can use binary search to narrow down the range of potential values for the kth smallest element by counting how many elements are less than or equal to a certain value. This helps us efficiently find the desired element.

def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
    n = len(matrix)
    # Set the range of the search to be between the smallest element
    # and the largest element in the matrix
    left, right = matrix[0][0], matrix[-1][-1]

    def less_k(mid):
        count = 0
        j = n - 1
        # Count the number of elements in the matrix
        # that are less than or equal to mid
        for i in range(n):
            while j >= 0 and matrix[i][j] > mid:
                j -= 1
            count += j + 1
        return count

    # Binary search for the kth smallest element
    while left < right:
        mid = left + (right - left) // 2
        # Update the range of the search
        if less_k(mid) < k:
            left = mid + 1
        else:
            right = mid

    return left

Explanation

  1. Initial Setup:
    • We determine the size of the matrix, n.
    • We define the search range for the kth smallest element between left (smallest element in the matrix) and right (largest element in the matrix).
  2. Helper Function less_k(mid):
    • This function counts the number of elements in the matrix that are less than or equal to mid.
    • We iterate through each row of the matrix and count how many elements in each row are less than or equal to mid.
  3. Binary Search:
    • We perform a binary search on the possible values of the kth smallest element.
    • We calculate the middle value mid of the current search range.
    • If the count of elements less than or equal to mid is less than k, we update left to mid + 1.
    • Otherwise, we update right to mid.
    • The process continues until left equals right, which gives us the kth smallest element.

Time Complexity: 𝑂(𝑛×log(max−min)) - The binary search runs in 𝑂(log(max−min)) time, where max and min are the maximum and minimum elements in the matrix, respectively. - For each iteration of the binary search, we count the number of elements less than or equal to mid in 𝑂(𝑛) time.

Space Complexity: 𝑂(1), The algorithm uses a constant amount of additional space.

Binary Search Result

Conclusion

In this article, we explored the problem of finding the kth smallest element in a sorted matrix. We discussed both the brute force and efficient binary search approaches, providing detailed explanations of the code and their complexities. While the brute force method is straightforward, the binary search approach leverages the sorted properties of the matrix to achieve a more time-efficient solution.

Understanding these methods enhances your problem-solving skills and prepares you for tackling similar challenges in coding interviews and competitions.

Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.

Next Articles in the Series