378. Kth Smallest Element in a Sorted Matrix – Leetcode Solutions

October 27, 2024

Table of Contents

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²).

Examples:

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

Solution in Python

Approach:

Binary Search on Values:
- Since each row and column of the matrix is sorted, the smallest element is at the top-left (matrix[0][0]) and the largest element is at the bottom-right (matrix[n-1][n-1]).
- This property allows us to apply binary search on the value range between matrix[0][0] and matrix[n-1][n-1] to find the kth smallest element without having to sort all elements.
Counting Elements:
- For each midpoint during the binary search, we need to count how many elements in the matrix are less than or equal to that midpoint. This count helps us decide whether to search in the left or right half.
- A helper function, count_less_equal(mid), can efficiently count elements less than or equal to a given value by using the sorted property of each row and column:
  - Start counting from the bottom-left element, moving upwards or to the right depending on whether the current element is less than or equal to mid.
Binary Search Process:
- Initialize left to matrix[0][0] and right to matrix[n-1][n-1].
- While left < right:
  - Calculate mid as the midpoint of left and right.
  - Use count_less_equal(mid) to count how many elements are less than or equal to mid.
  - If the count is less than k, adjust left = mid + 1 to move the search to the right half (looking for larger values).
  - Otherwise, adjust right = mid to move the search to the left half.
Final Result:
- Once left == right, we have narrowed down the kth smallest element.

Python

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        # Helper function to count elements <= mid in the matrix
        def count_less_equal(mid):
            count = 0
            row, col = len(matrix) - 1, 0  # Start from the bottom-left corner
            
            while row >= 0 and col < len(matrix):
                if matrix[row][col] <= mid:
                    # All elements in the current row up to col are <= mid
                    count += row + 1
                    col += 1
                else:
                    # Move up to find smaller elements
                    row -= 1
            
            return count

        # Binary search on the values in the matrix
        left, right = matrix[0][0], matrix[-1][-1]
        
        while left < right:
            mid = (left + right) // 2
            if count_less_equal(mid) < k:
                # Fewer than k elements are <= mid, move right
                left = mid + 1
            else:
                # At least k elements are <= mid, move left
                right = mid
        
        # When left == right, we've found the kth smallest element
        return left

Explanation of the Code:

count_less_equal(mid):
- This helper function counts how many elements in the matrix are less than or equal to mid by starting from the bottom-left of the matrix.
- For each element at matrix[row][col]:
  - If it’s less than or equal to mid, all elements above it in the current column are also less than or equal to mid. So we add row + 1 to the count and move to the right.
  - If it’s greater than mid, we move one row up to check smaller values in the current column.
Binary Search:
- left is initialized to the smallest value, matrix[0][0], and right to the largest, matrix[-1][-1].
- At each step, mid is the midpoint of left and right, and we count elements <= mid.
- Depending on the count, we adjust left or right to continue narrowing down the search range until left == right.
Result:
- When left == right, the search concludes, and left (or right) holds the kth smallest element.

Solution in C++

C++

class Solution {
public:
    // Helper function to count elements in the matrix that are less than or equal to a given value
    int countLessEqual(const vector<vector<int>>& matrix, int mid, int n) {
        int count = 0;
        int row = n - 1;  // Start from the bottom-left corner of the matrix
        int col = 0;

        // Traverse upwards and rightwards to count elements <= mid
        while (row >= 0 && col < n) {
            if (matrix[row][col] <= mid) {
                // All elements in this row up to the current position are <= mid
                count += (row + 1);
                col++;  // Move to the next column
            } else {
                // Move up to find smaller elements
                row--;
            }
        }
        return count;
    }

    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();  // Dimension of the matrix (n x n)
        int left = matrix[0][0];  // Smallest element in the matrix
        int right = matrix[n - 1][n - 1];  // Largest element in the matrix

        // Binary search for the kth smallest element
        while (left < right) {
            int mid = left + (right - left) / 2;

            // Count how many numbers are less than or equal to mid
            int count = countLessEqual(matrix, mid, n);

            if (count < k) {
                // If count is less than k, we need to search in the larger half
                left = mid + 1;
            } else {
                // If count is greater than or equal to k, search in the smaller half
                right = mid;
            }
        }

        // 'left' is now the kth smallest element
        return left;
    }
};

Solution in Javascript

JavaScript

var kthSmallest = function(matrix, k) {
    // Define the search range for the binary search
    let left = matrix[0][0]; // smallest element in the matrix
    let right = matrix[matrix.length - 1][matrix[0].length - 1]; // largest element in the matrix
    
    // Binary search for the kth smallest element
    while (left < right) {
        // Find the middle element of the current range
        const mid = Math.floor((left + right) / 2);
        
        // Count how many elements in the matrix are less than or equal to `mid`
        let count = countLessEqual(matrix, mid);
        
        if (count < k) {
            // If there are fewer than k elements less than or equal to mid,
            // we need to search in the higher range
            left = mid + 1;
        } else {
            // Otherwise, we search in the lower range
            right = mid;
        }
    }
    
    // After the loop, `left` will point to the kth smallest element
    return left;
};

function countLessEqual(matrix, x) {
    let count = 0;
    let n = matrix.length;
    let row = n - 1; // start from the last row
    let col = 0;     // start from the first column
    
    // Traverse the matrix in a zig-zag manner (bottom-left to top-right)
    while (row >= 0 && col < n) {
        if (matrix[row][col] <= x) {
            // If the element is <= x, all elements in this row up to this column
            // are also <= x (since each row is sorted), so add `row + 1` to the count
            count += row + 1;
            col++;
        } else {
            // Otherwise, move up to the next row
            row--;
        }
    }
    
    return count;
}

Solution in Java

Java

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        // Define the initial range of possible values in the matrix
        int n = matrix.length;
        int left = matrix[0][0];  // Smallest element in the matrix
        int right = matrix[n - 1][n - 1];  // Largest element in the matrix

        // Perform binary search on the value range
        while (left < right) {
            int mid = left + (right - left) / 2;  // Find the midpoint of the current range
            
            // Count how many elements in the matrix are less than or equal to mid
            int count = countLessEqual(matrix, mid, n);
            
            // If count is less than k, search in the upper half of the range
            if (count < k) {
                left = mid + 1;
            } else {
                // Otherwise, search in the lower half of the range
                right = mid;
            }
        }
        
        // After the loop, left and right converge to the kth smallest element
        return left;
    }

    // Helper function to count elements <= target in the matrix
    private int countLessEqual(int[][] matrix, int target, int n) {
        int count = 0;
        int row = n - 1;  // Start from the last row
        int col = 0;  // Start from the first column

        // Traverse the matrix in a "staircase" manner
        while (row >= 0 && col < n) {
            if (matrix[row][col] <= target) {
                // If the element is <= target, all elements above in this column are also <= target
                count += (row + 1);
                col++;  // Move to the next column
            } else {
                row--;  // Move up in the same column to find smaller elements
            }
        }
        
        return count;
    }
}

378. Kth Smallest Element in a Sorted Matrix – Leetcode Solutions

Description

Solution in Python

Approach:

Explanation of the Code:

Solution in C++

Solution in Javascript

Solution in Java

Popular

116. Populating Next Right Pointers in Each Node – Leetcode Solutions

49. Group Anagrams – Leetcode Solutions

28. Find the Index of the First Occurrence in a String – Leetcode Solution

326. Power of Three – Leetcode Solutions

402. Remove K Digits – Leetcode Solutions

313. Super Ugly Number – Leetcode Solutions

1920. Build Array from Permutation – Solutions

378. Kth Smallest Element in a Sorted Matrix – Leetcode Solutions

Description

Solution in Python

Approach:

Explanation of the Code:

Solution in C++

Solution in Javascript

Solution in Java

Related Post

Popular