Kth element in Matrix

JavaView on GFG

Intuition

Find kth smallest element in row-wise and column-wise sorted matrix. Binary search on value.

Algorithm

1Binary search on value range [matrix[0][0], matrix[n-1][n-1]]. For mid: count elements <= mid.
2Count using staircase from top-right: O(n) per count.

Common Pitfalls

•Same as LC 378. Binary search on answer, not index. Count <= mid in O(n).

Kth element in Matrix.java

Java

// Approach: Binary search on value. Count elements <= mid in O(n) row-by-row. Narrow until kth element found.
// Time: O(n log(max-min)) Space: O(1)
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int low = matrix[0][0];
        int high = matrix[n - 1][n - 1];

        while (low < high) {
            int mid = low + (high - low) / 2;
            int count = countLessEqual(matrix, mid);

            if (count < k)
                low = mid + 1;
            else
                high = mid;
        }

        return low;
    }

    private int countLessEqual(int[][] matrix, int target) {
        int n = matrix.length;
        int count = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] <= target)
                    count++;
            }
        }

        return count;
    }
}

Was this solution helpful?