Business
Jobs
  • About Us
  • Solutions
    • Job Postings
      Post your job and receive qualified candidates in 48h.
    • Candidate Assessments
      500+ technical and psychological tests, plus anti-fraud.
    • Headhunting
      Tailor-made executive search from start to finish.
    • Payroll + EOR
      Payroll dispersal and EOR across 15+ LATAM countries.
  • Pricing
  • Jobs

0

154
Views
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

about 4 years ago · Juan Pablo Isaza
2 answers
Answer question

0

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)

about 4 years ago · Juan Pablo Isaza Report

0

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)
about 4 years ago · Juan Pablo Isaza Report
Answer question
Find remote jobs

Discover the new way to find a job!

Top jobs
Top job categories
Business
Post vacancy Pricing Sales
Legal
Terms and conditions Privacy policy
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Show me some job opportunities
There's an error!