Log(max-min) * n * Log(n). Binary search. Java


  • 0
    A

    Timr complexity is log(max-min)nlog(n); In the first binary search we fix the answer. Then we will count how many numbers from each row are less than this fixed value. To count the less or equal values In order to traverse the whole row we can use here also binary search.

    public 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];
            
            int ans = matrix[0][0];
            while (low<=high) {
                int mid = low + (high - low)/2;
                int val = getLessEqual(matrix, mid);
                if (val<k) {
                    low = mid + 1;
                    ans = mid;
                } else {
                    high = mid -1;
                }
            }
            return low;
        }
        
        private int getLessEqual(int matrix[][], int val) {
            int n = matrix[0].length;
            int cnt = 0;
            for (int i=0; i<n; i++) {
                int L = 0;
                int R = n-1; 
                int pos = -1;
                while (L<=R) {
                    int mid = L + (R-L)/2;
                    if (matrix[i][mid]<=val) {
                        L = mid + 1;
                        pos = mid;
                    } else {
                        R = mid - 1;
                    }
                }
                cnt+=pos+1;
            }
            return cnt;
        }
    }
    

  • 0
    V

    Can you please post the proof of correctness? specially, How can you claim that your low exists in your matrix?


Log in to reply
 

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