Javascript way of Kth Smallest Element in a Sorted Matrix-CodePudding

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

CodePudding user response：

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)

CodePudding user response：

This line in regards to "what is this code line doing please help me find out"

 mid = (lo   (hi - lo) / 2) >> 0;

Looks like a part of a "binary search", akin to the guessing number game higher or lower. The code above is getting the "middle" value to keep searching.

As such and if so, the data to search must already be sorted.