trying to solve Kth Smallest Element in a Sorted Matrix,basically You found a solution with a memory complexity better than O(n2).
Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13
what is this code line doing please help me find out???
mid = (lo + (hi - lo) / 2) >> 0;
Here is full code
var kthSmallest = function(matrix, k) {
var n = matrix.length, lo = matrix[0][0]
var hi = matrix[n-1][n-1];
var mid, count;
while(lo < hi) {
mid = (lo + (hi - lo) / 2) >> 0;
count = countLEQ(matrix, mid);
if (count < k) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
};
var countLEQ = function (matrix, x) {
var n = matrix.length;
var count = 0;
var j;
matrix.forEach(function(row){
for(j = 0; j < n && row[j] <= x; j++){ ;}
count += j
});
return count;
};
Am i right in saying Time complexity as O(log n) as its binary search algorithm ???
Your help is appreciated
Carolyn
Time complexity is between O(log n) and O(n), since while the outer loop is indeed a binary search (O(log n)), the countLEQ method is serial (O(n)).
This line:
mid = (lo + (hi - lo) / 2) >> 0
Just calculates a new mid point, truncating any fractions. Shift right >> 0 does this by converting to int. This is usually done using the double tilde operator (~~): i.e. mid = ~~(lo + (hi - lo) / 2)
mid = (lo + (hi - lo) / 2) >> 0
This is used for calculating the mid index in a binary search. It is avoiding any fraction values.
Alternative Method for calculating mid index in a binary search :
Math.floor((lo + hi) / 2)