Thinking process I -- Heap

Given a sorted matrix, how to find the kth smallest?

• the matrix is special, each row and column is sorted in ascending order
• which means, if x must be smaller than the one on its right and the one on its left

how to get the min/max from finite number of integers.

• heap
  • add O(log n)
  • poll O(1)

Mistakes

encapsulation

• class Cell
• not private or public class Cell

index

• count < k - 1
• not cont < k

Time Complexity

O (k log k)

API Method

Comparator interface

class className implements Comparator<Type> {
    public int compare (Type a, Type b) {
        //ascending order
        return a.val - b.val;

        //descending order
        if (a.val < b.val) {
            return 1;
        } else if (a.val > b.val) {
            return -1;
        } else {
            return 0;
        }
    }
}

PriorityQueue init with custom comparator

https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

PriorityQueue<Cell> pq = new PriorityQueue<Cell>(1, new CellComparator());

>>>>>>>>Code

class Cell {
    public int x;
    public int y;
    public int val;

    public Cell (int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }
}

class CellComparator implements Comparator<Cell> {
    public int compare(Cell a, Cell b) {
        return a.val - b.val;
    }
}

public class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        //validate input and check corner cases
        if (matrix.length == 0 || matrix[0].length == 0) return 0;

        int n = matrix.length;
        int m = matrix[0].length;

        PriorityQueue<Cell> pq = new PriorityQueue<Cell>(1, new CellComparator());//min heap
        pq.add(new Cell(0, 0, matrix[0][0]));

        boolean[][] visited = new boolean[n][m];
        visited[0][0] = true;

        int count = 0;

        while (!pq.isEmpty() && count < k - 1) {
            Cell c = pq.poll();

            if (c.x + 1 < n && !visited[c.x + 1][c.y]) {
                pq.add(new Cell(c.x + 1, c.y, matrix[c.x + 1][c.y]));
                visited[c.x + 1][c.y] = true;
            }
            if (c.y + 1 < m && !visited[c.x][c.y + 1]) {
                pq.add(new Cell(c.x, c.y + 1, matrix[c.x][c.y + 1]));
                visited[c.x][c.y + 1] = true;
            }

            count++;
        }

        return pq.poll().val;
    }
}

Thinking Process II -- Binary search

https://discuss.leetcode.com/topic/52948/share-my-thoughts-and-clean-java-code

The post above mentioned that The key point for any binary search is to figure out the "Search Space". There are two kind of "Search Space" -- index and range(the range from the smallest number to the biggest number). Most usually, when the array is sorted in one direction, we can use index as "search space", when the array is unsorted and we are going to find a specific number, we can use "range".

• Search by range

Mistakes

How to make sure that this number is actually in the matrix?

• In helper function, count the numbers that are less or equal to num
• Because, in this case, comparing with k, the current one should be the one that is kth

In the helper function, how to count the numbers that are less or equal to num?

• using for loop is not flexible, instead using while loop.

Out of the loop, what to return?

• Instead of checking the count(left) <= k, it should be larger or equals to k
• Because, what if there are duplicates?
• Thinking about this case, [[1,2], [1,3]] find the first

Time Complexity

O (n x n log n)

public class Solution {

    private int count(int num, int[][] matrix) {
        //count all numbers that is less than or equal to num

        int n = matrix.length;
        int m = matrix[0].length;
        int total = m * n;

        int i = n - 1;
        int j = 0;

        while (i >= 0 && j < m) {
            if (matrix[i][j] > num) {
                total -= (m - j);
                i--;
            } else {
                j++;
            }
        }

        return total;
    }

    public int kthSmallest(int[][] matrix, int k) {
        if (matrix.length == 0 || matrix[0].length == 0) return 0;

        int n = matrix.length;
        int m = matrix[0].length;
        int l = matrix[0][0];
        int r = matrix[n - 1][m - 1];

        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            System.out.println(mid);

            if (count(mid, matrix) < k) {
                l = mid;
            } else {
                r = mid;
            }
        }

        if (count(l, matrix) >= k) {
            return l;
        }

        return r;
    }
}