Java 1ms nlog(max -min) solution


  • 46
    J

    Main loop is binary search of max - min.
    Swap from left-bottom to right-top can get count <= mid in O(n) time instead of O(nlogn), total complexity will be O(nlogm) while m = max - min.

    public class Solution {
        public int kthSmallest(int[][] matrix, int k) {
            int n = matrix.length;
            int lo = matrix[0][0], hi = matrix[n - 1][n - 1];
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                int count = getLessEqual(matrix, mid);
                if (count < k) lo = mid + 1;
                else hi = mid - 1;
            }
            return lo;
        }
        
        private int getLessEqual(int[][] matrix, int val) {
            int res = 0;
            int n = matrix.length, i = n - 1, j = 0;
            while (i >= 0 && j < n) {
                if (matrix[i][j] > val) i--;
                else {
                    res += i + 1;
                    j++;
                }
            }
            return res;
        }
    }
    

  • 0
    J

    simplified to one pass


  • 0

    @jiangbowei2010 said in Java 1ms nlog(max -min) solution:

    while (lo <= hi) {

    lo < hi is enough.


  • 1

    @zhugejunwei

    public class Solution {
        public int kthSmallest(int[][] matrix, int k) {
            int n = matrix.length;
            int l = matrix[0][0], h = matrix[n-1][n-1];
            while (l < h) {
                int m = l + (h - l)/2;
                int count = binarySearch(matrix, m);
                if (count < k) {
                    l = m + 1;
                } else {
                    h = m;
                }
            }
            return l;
        }
        public int binarySearch(int[][] matrix, int target) {
            int n = matrix.length, i = n-1, j = 0;
            int res = 0;
            while (i >= 0 && j <= n-1) {
                if (matrix[i][j] > target) i--;
                else {
                    j++;
                    res += i + 1;
                }
            }
            return res;
        }
    }
    

  • 7
    X

    I have a question, when you do binary search on max - min, how could your binary search guarantee to return a number that exists in the input matrix?


  • 1
    L

    @xuefei1 The binary search used here is to shrink the search range roughly by half. When the search range has only one element, the result is that element. Hope this helps your understanding.


  • 3
    Z

    @xuefei1 Adding on to @luofei 's answer. The element found by this algorithm has to be in the input matrix because the range converges to the minimum value that satisfies (or most closely follows) the condition count == k. The first value to satisfy count == k must be found in the range if exists.


  • 2

    res += i + 1;
    I think this step is really the most important part in this solution.


  • 0
    W

    Smart solution. One of the keys is to go to the floor instead of ceiling when getting k elements, which is this line else { hi = mid -1} . Otherwise we may end up having k + x th element where x is the number of elements that have same value as kth number.


  • 1
    N

    @xuefei1 I have read comments from both @luofei and @zipte89, but I still could not get it. Then, I thought a prove like below:

    If the mid variable converges to an integer, a_mid, which is not the kth smallest element, a_k, in the array.
    Then, a_mid should be bigger than a_k, if not the count will be less than k and a_mid will increase.
    Therefore, lo<=a_k<a_mid<=hi will be true, and the loop ends at lo=hi, which means a_mid has to equal to a_k.

    Looks like a squeeze theorem.


  • 0

    @zipte89 This makes so much sense. Been busting my head on this for so long until seen your explanation. Tks for sharing, upvoted.


  • 0

    For those who do not understand why countLessEqual is calculated this way, consider how mid partitions each row:

    *   *   *   * | *
    *   *   * | *   *
    *   *   * | *   *
    *   * | *   *   *
    * | *   *   *   *
    *   *   *   *   *
    

    As long as you traverse along this diagonal direction, you do not need to go backwards when you move to a new row;

    Op's approach starts from the leftbottom corner; the other most voted solutions does the count from the topright corner. Both equivalent tho.


  • 0
    A

    @zhugejunwei No it's not enough. Try case matrix = [[1,2],[1,3]] and k = 3


  • 0
    4
    This post is deleted!

  • 0
    4
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.