378. Kth Smallest Element in a Sorted Matrix (Medium)

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

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

return 13.

Note:
You may assume k is always valid, 1 ≤ k ≤ n2.

Solutions

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        // corner case, matrix
        if (matrix == null || matrix.length == 0) {
            return -1;
        }

        int row = matrix.length;

        // what if not nxn matrix, to make the solution more flexible, take column size into account.
        int col = matrix[0].length;

        // corner case k
        if (k >= row * col) {
            return matrix[row-1][col-1];
        }

        // keep track of the head pointer for each row in matrix
        int[] headers = new int[row];
        Arrays.fill(headers, 0);

        // set a count for the visited values
        int count = 0;

        while (count < row * col) {

            // Define smallest row id r, smallest col id c, and minimum value min

            // Do not set it with the first row's in case the first row already searched through
            // such that overstep the boundary.
            int r = -1;
            int c = -1;
            int min = Integer.MAX_VALUE;

            // go through the matrix row by row
            for (int i = 0; i < row; i++) {
                // all elements are scanned through, skip to next row

                if (headers[i] >= col) {
                    continue;
                }

                // every time pick one smallest element from all the matrix rows

                if (r == -1) {
                    r = i;
                    c = headers[i];
                    min = matrix[r][c];

                    continue;
                }

                if (min <= matrix[i][headers[i]]) {
                    continue;
                }

                r = i;
                c = headers[i];
                min = matrix[r][c];
            }

            // increase head pointer of row matrix[r]
            headers[r]++;

            count++;

            // if count == k, return current value in matrix[r][c]
            if (count == k) {
                return matrix[r][c];
            }
        }

        // Execution will never make it here.

        return -1;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-03 11:01:17

results matching ""

    No results matching ""