378. Kth Smallest Element in a Sorted Matrix

Problem Description

Given an n x n matrix where each row and column 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(n²).

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].length
• 1 <= n <= 300
• -10⁹ <= matrix[i][j] <= 10⁹
• All the rows and columns of matrix are guaranteed to be sorted in ascending order
• 1 <= k <= n²

Python Solution

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        n = len(matrix)
        
        def count_smaller_equal(mid):
            count = 0
            row, col = n - 1, 0
            
            # Start from bottom-left corner
            while row >= 0 and col < n:
                if matrix[row][col] <= mid:
                    # Add count of all elements in this column up to row
                    count += row + 1
                    col += 1
                else:
                    row -= 1
            
            return count
        
        # Binary search on the range of possible values
        left = matrix[0][0]  # Smallest possible value
        right = matrix[n-1][n-1]  # Largest possible value
        
        while left < right:
            mid = left + (right - left) // 2
            count = count_smaller_equal(mid)
            
            if count < k:
                left = mid + 1
            else:
                right = mid
        
        return left

Java Solution

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0];
        int right = matrix[n-1][n-1];
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = countSmallerEqual(matrix, mid);
            
            if (count < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
    
    private int countSmallerEqual(int[][] matrix, int mid) {
        int n = matrix.length;
        int count = 0;
        int row = n - 1;
        int col = 0;
        
        // Start from bottom-left corner
        while (row >= 0 && col < n) {
            if (matrix[row][col] <= mid) {
                // Add count of all elements in this column up to row
                count += row + 1;
                col++;
            } else {
                row--;
            }
        }
        
        return count;
    }
}

C++ Solution

class Solution {
public:
    int kthSmallest(vector>& matrix, int k) {
        int n = matrix.size();
        int left = matrix[0][0];
        int right = matrix[n-1][n-1];
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = countSmallerEqual(matrix, mid);
            
            if (count < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
    
private:
    int countSmallerEqual(vector>& matrix, int mid) {
        int n = matrix.size();
        int count = 0;
        int row = n - 1;
        int col = 0;
        
        // Start from bottom-left corner
        while (row >= 0 && col < n) {
            if (matrix[row][col] <= mid) {
                // Add count of all elements in this column up to row
                count += row + 1;
                col++;
            } else {
                row--;
            }
        }
        
        return count;
    }
};

JavaScript Solution

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(matrix, k) {
    const n = matrix.length;
    let left = matrix[0][0];
    let right = matrix[n-1][n-1];
    
    const countSmallerEqual = (mid) => {
        let count = 0;
        let row = n - 1;
        let col = 0;
        
        // Start from bottom-left corner
        while (row >= 0 && col < n) {
            if (matrix[row][col] <= mid) {
                // Add count of all elements in this column up to row
                count += row + 1;
                col++;
            } else {
                row--;
            }
        }
        
        return count;
    };
    
    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);
        const count = countSmallerEqual(mid);
        
        if (count < k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
};

C# Solution

public class Solution {
    public int KthSmallest(int[][] matrix, int k) {
        int n = matrix.Length;
        int left = matrix[0][0];
        int right = matrix[n-1][n-1];
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = CountSmallerEqual(matrix, mid);
            
            if (count < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
    
    private int CountSmallerEqual(int[][] matrix, int mid) {
        int n = matrix.Length;
        int count = 0;
        int row = n - 1;
        int col = 0;
        
        // Start from bottom-left corner
        while (row >= 0 && col < n) {
            if (matrix[row][col] <= mid) {
                // Add count of all elements in this column up to row
                count += row + 1;
                col++;
            } else {
                row--;
            }
        }
        
        return count;
    }
}