Kth Smallest Element in a Sorted Matrix (Row and Column Sorted Matrix)

• Kth Smallest in a Sorted Matrix treats each row as a sorted list and applies early-stopped K-way Merge.
• A min-heap is seeded with the first element of each row, carrying {value, row, col}.
• We pop K times, pushing the next column element from the same row after each pop.
• The Kth popped value is the answer.
• Only the row-sorted property is needed; column-sorted is not required for this approach.
• Time is O(K log N) and space is O(N) for an N-by-N matrix.

What is the Kth Smallest in a Sorted Matrix problem?

Given an N-by-N matrix where each row and each column is sorted in ascending order, find the Kth smallest element overall. This combines the concepts of matrix traversal and priority-based selection.

For example, given the matrix [[1, 5, 9], [10, 11, 13], [12, 13, 15]] and K = 8, the sorted order is [1, 5, 9, 10, 11, 12, 13, 13, 15], so the 8th smallest is 13.

How does the K-way Merge approach work?

Since each row is already sorted, the matrix is essentially N sorted lists. We use a min-heap seeded with the first element (column 0) of each row. The heap entry stores {value, row, col}. We pop K times, and after each pop we push the next element from the same row (column + 1) if it exists.

package com.bank.service;

import java.util.PriorityQueue;

public class KthSmallestMatrixService {

    /**
     * Finds the Kth smallest fee in the National Bank of India fee grid.
     * Each row and column of the grid is sorted in ascending order.
     */
    public static int kthSmallest(int[][] feeGrid, int k) {
        int n = feeGrid.length;
        // Heap entry: {value, row, col}
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
            (a, b) -> Integer.compare(a[0], b[0]));

        // Seed with column 0 of each row
        for (int r = 0; r < n; r++) {
            minHeap.offer(new int[]{feeGrid[r][0], r, 0});
        }

        int result = 0;
        for (int i = 0; i < k; i++) {
            int[] entry = minHeap.poll();
            result = entry[0];
            int row = entry[1], col = entry[2];

            // Push next element from the same row
            if (col + 1 < n) {
                minHeap.offer(new int[]{feeGrid[row][col + 1], row, col + 1});
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[][] feeGrid = {
            {100, 500, 900},
            {200, 600, 1000},
            {400, 700, 1100}
        };
        int k = 5;
        System.out.println("Kth smallest fee (K=" + k + "): "
            + kthSmallest(feeGrid, k));
    }
}

javac -d out com/bank/service/KthSmallestMatrixService.java
java -cp out com.bank.service.KthSmallestMatrixService

Kth smallest fee (K=5): 600

Why is only the row-sorted property needed?

The K-way merge treats each row as an independent sorted list. It does not use the column-sorted property at all. The column-sorted property is a nice bonus the problem gives, but the heap merge depends only on each row being sorted so that the next element in a row is always greater than or equal to the current one.

This is an important point interviewers like to probe: understanding which property your algorithm actually relies on.

What is the binary search alternative?

An alternative approach binary-searches on the value range [matrix[0][0], matrix[n-1][n-1]]. For a candidate value mid, count how many elements in the matrix are less than or equal to mid by walking from the bottom-left corner. If the count is less than K, search higher; otherwise search lower.

package com.bank.service;

public class KthSmallestBinarySearch {

    public static int kthSmallest(int[][] grid, int k) {
        int n = grid.length;
        int low = grid[0][0], high = grid[n - 1][n - 1];

        while (low < high) {
            int mid = low + (high - low) / 2;
            int count = countLessOrEqual(grid, mid, n);
            if (count < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }

    private static int countLessOrEqual(int[][] grid, int target, int n) {
        int count = 0;
        int row = n - 1, col = 0;
        while (row >= 0 && col < n) {
            if (grid[row][col] <= target) {
                count += row + 1; // All elements above in this column
                col++;
            } else {
                row--;
            }
        }
        return count;
    }
}

How do the two approaches compare?

| Aspect | K-way Merge (Heap) | Binary Search on Value |
|---|---|---|
| Time | O(K log N) | O(N log(max - min)) |
| Space | O(N) | O(1) |
| Better when | K is small relative to N^2 | K is large or close to N^2 |
| Uses column-sorted? | No | Yes (for counting) |

What are the edge cases?

Several edge cases require attention.

• K = 1: the answer is always matrix[0][0], the top-left element.
• K = N^2: the answer is always matrix[N-1][N-1], the bottom-right element.
• 1x1 matrix: the answer is the single element.
• All elements equal: any K gives the same value.

package com.bank.core;

public class KthSmallestEdgeCases {
    public static void main(String[] args) {
        int[][] grid = {{100, 200}, {300, 400}};
        System.out.println("K=1: " + KthSmallestMatrixService.kthSmallest(grid, 1)); // 100
        System.out.println("K=4: " + KthSmallestMatrixService.kthSmallest(grid, 4)); // 400
    }
}

K=1: 100
K=4: 400

What is the time and space complexity?

For the heap approach: the heap holds at most N elements (one per row), so K pops cost O(K log N) time. Space is O(N). For the binary search approach: each counting pass takes O(N) time, and we do O(log(max - min)) passes, giving O(N log(max - min)) time with O(1) extra space.

What should a senior engineer know?

A senior engineer should understand these deeper aspects.

• Optimized seeding: seed only min(N, K) rows because no element below row K can be among the first K smallest.
• Binary search correctness: the binary search converges to an actual matrix value because at each step we narrow to a range that must contain an element.
• Young tableau: a matrix sorted by both rows and columns is called a Young tableau, and there are specialized algorithms for insertion and deletion in O(N) time.