How to Solve Kth Smallest Element in a Sorted Matrix

The kth smallest element in a sorted matrix can be found using binary search over the value range or a min-heap traversal. Start by defining the search space between the smallest and largest matrix elements and iteratively count elements less than midpoints. Heap-based approaches maintain a priority queue of potential next smallest elements to extract the kth value efficiently while keeping memory usage under control.

Problem Statement

Given an n x n matrix where each row and each column is sorted in ascending order, identify the kth smallest element considering the full sorted order. The element to return is based on the sorted position, not uniqueness, and must be computed efficiently without storing all matrix elements.

Implement a function that takes an n x n sorted matrix and an integer k, and returns the kth smallest element. Solutions should optimize memory beyond O(n^2), handling matrices up to size 300x300 with elements ranging from -10^9 to 10^9, ensuring correct counting even when duplicates exist.

Examples

Example 1

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

Output: 13

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

Example details omitted.

Constraints

• n == matrix.length == matrix[i].length
• 1 <= n <= 300
• -109 <= matrix[i][j] <= 109
• All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
• 1 <= k <= n2

Solution Approach

Binary Search Over Value Range

Use the smallest and largest matrix elements as low and high bounds. Perform binary search on this range, counting elements less than or equal to the mid-value at each step. Narrow the bounds until the kth smallest element is identified. This pattern avoids full sorting and optimizes memory usage.

Min-Heap Traversal

Initialize a min-heap with the first element of each row. Repeatedly pop the smallest element and push the next element from the same row until k elements are popped. This approach ensures the kth smallest is extracted without flattening the matrix, directly reflecting the problem's priority queue pattern.

Counting Function Optimization

Implement a helper function to count elements less than or equal to a given target using row-wise iteration from bottom-left or top-right. This counting informs the binary search decision efficiently, leveraging the matrix's sorted properties to avoid unnecessary traversal.

Complexity Analysis

Binary search approach has O(n log(max-min)) time, where max and min are the matrix extremes, and O(1) space. Min-heap method requires O(k log n) time and O(n) space for the heap. Counting function optimizes the binary search by avoiding full matrix flattening, reducing runtime significantly for large n.

What Interviewers Usually Probe

• Asks how to improve from O(n^2) memory to O(n) using matrix properties.
• Probes whether you can count elements without flattening the matrix.
• Checks if binary search on values versus indices is understood and correctly implemented.

Common Pitfalls or Variants

Common pitfalls

• Flattening the matrix and sorting uses excessive memory and ignores constraints.
• Miscounting elements when duplicates exist, which can return the wrong kth element.
• Confusing kth smallest with kth distinct element, leading to incorrect output.

Follow-up variants

• Find the kth largest element in a sorted matrix using similar binary search logic.
• Handle rectangular matrices where rows and columns are sorted differently.
• Adapt heap solution to track positions in multiple sorted arrays or merged lists.

How GhostInterview Helps

• GhostInterview highlights the optimal binary search bounds and counting strategy specific to sorted matrices.
• Provides heap-based solutions with step-by-step push/pop operations to track the kth smallest element efficiently.
• Guides through pitfalls like duplicates and memory usage, ensuring the solution pattern aligns with the interview's expectation.

Topic Pages

• Array
• Binary Search
• Sorting
• Heap (Priority Queue)
• Matrix

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the best approach for Kth Smallest Element in a Sorted Matrix?

Use binary search over the value range with a counting function or a min-heap traversal for efficient memory usage.

Can duplicates affect the kth smallest element solution?

Yes, duplicates require careful counting to ensure the kth smallest in sorted order is correct, not just distinct elements.

What is the space complexity of the binary search method?

Binary search requires O(1) extra space beyond the input, leveraging the matrix's inherent sorted structure.

Is flattening the matrix a recommended strategy?

No, flattening uses O(n^2) memory and ignores constraints; optimized binary search or heap methods are preferred.

How does GhostInterview help with the binary search pattern?

It provides guided counting functions, boundary setup, and iterative narrowing steps tailored to sorted matrices, reducing errors and runtime.