Kth Smallest Element in a Sorted Matrix - Practice Coding Problems

Kth Smallest Element in a Sorted Matrix - Problem

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

Input & Output

Example 1 — Basic 3x3 Matrix

$ Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8

› Output: 13

💡 Note: The elements in sorted order are [1,5,9,10,11,12,13,13,15]. The 8th smallest is 13.

Example 2 — Small Matrix

$ Input: matrix = [[-5]], k = 1

› Output: -5

💡 Note: Single element matrix, the 1st (and only) smallest element is -5.

Example 3 — First Element

$ Input: matrix = [[1,2],[1,3]], k = 1

› Output: 1

💡 Note: Elements in order: [1,1,2,3]. The 1st smallest is 1 (top-left).

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 non-decreasing order
1 ≤ k ≤ n²

Visualization

Tap to expand

Understanding the Visualization

Input

Sorted matrix and k=8

Process

Find 8th smallest efficiently

Output

Return the element value

Key Takeaway

🎯 Key Insight: Instead of sorting all elements, leverage the matrix's sorted structure to find the kth smallest efficiently using binary search on answer values or heap-based selection.

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The optimal solution uses binary search on the answer space with O(n log(max-min)) time and O(1) space. The key insight is to search for the answer value rather than extracting elements, using the matrix's sorted property to efficiently count elements ≤ any target value.

Common Approaches

Approach	Time	Space	Notes
✓ Binary Search on Answer Space	O(n log(max - min))	O(1)	Binary search on possible answer values while counting elements ≤ mid
Brute Force - Flatten and Sort	O(n² log n)	O(n²)	Extract all elements, sort them, and return the kth element
Min Heap Approach	O(k log(min(k, n)))	O(min(k, n))	Use a min heap to efficiently find the kth smallest element

Binary Search on Answer Space — Algorithm Steps

Set search range from smallest to largest element in matrix
For each middle value, count elements ≤ mid using matrix's sorted property
If count ≥ k, search lower half; otherwise search upper half

Visualization

Tap to expand

Step-by-Step Walkthrough

Range

Set search range [1, 15]

Count

For mid=8, count elements ≤ 8

Narrow

Adjust range based on count vs k

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int countLessEqual(int** matrix, int matrixSize, int target) {
    int count = 0;
    int row = matrixSize - 1, col = 0;
    
    while (row >= 0 && col < matrixSize) {
        if (matrix[row][col] <= target) {
            count += row + 1;
            col++;
        } else {
            row--;
        }
    }
    
    return count;
}

int solution(int** matrix, int matrixSize, int* matrixColSize, int k) {
    if (matrixSize == 0) return 0;
    
    int left = matrix[0][0];
    int right = matrix[matrixSize-1][matrixSize-1];
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (countLessEqual(matrix, matrixSize, mid) < k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
}

int main() {
    int matrix[3][3] = {{1,5,9},{10,11,13},{12,13,15}};
    int* rows[3] = {matrix[0], matrix[1], matrix[2]};
    int colSizes[3] = {3, 3, 3};
    int k = 8;
    
    printf("%d\n", solution(rows, 3, colSizes, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log(max - min))

Binary search has log(max-min) iterations, each counting step takes O(n) using matrix properties

⚡ Linearithmic

Space Complexity

O(1)

Only uses constant extra space for variables

✓ Linear Space

78.5K Views

Medium Frequency

~25 min Avg. Time

3.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Binary Search on Answer Space — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler