Empresas
Empregos
  • Sobre nós
  • Soluções
    • Publicação de vagas
      Publique sua vaga e receba candidatos qualificados em 48h.
    • Avaliações de candidatos
      Mais de 500 testes técnicos e psicológicos, mais anti-fraude.
    • Headhunting
      Busca executiva personalizada do início ao fim.
    • Folha de Pagamento + EOR
      Dispersão de folha e EOR em mais de 15 países da LATAM.
  • Preços
  • Empregos

0

156
Visualizações
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 Respostas
Responde à pergunta

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 Relatório

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 Relatório
Responde à pergunta
Encontrar trabalhos remotos

Descubra a nova forma de encontrar um emprego!

melhores empregos
Principais categorias de trabalho
Empresas
Postar vaga Preços Comercial
Jurídico
Termos e Condições Política de privacidade
© 2026 PeakU Inc. All Rights Reserved.
Andres GPT
Recomende algumas ofertas para mim
Preciso de ajuda