CODEWITHSUNDEEP
javascriptdata-structuresecmascript-6
Carolyn Cordeiro
Carolyn Cordeiro

Reputation: 1905

Javascript way of Kth Smallest Element in a Sorted Matrix

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

Upvotes: 0

Views: 151

Answers (2)

sakigo
sakigo

Reputation: 111

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)

Upvotes: 0

Tibrogargan
Tibrogargan

Reputation: 4603

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)

Upvotes: 1

Related Questions