CODEWITHSUNDEEP
javascriptarraysnode.js
Emad Dehnavi
Emad Dehnavi

Reputation: 3441

Finding total number of maximum number in array fail only for big data

I doing some Hackerrank challange to improve my problem solving skills, so one of the challanges was about finding the total maximum numbers from an array of numbers. For example if we have 3 2 1 3 1 3 it should return 3

This is what I did : 

function birthdayCakeCandles(ar) {
let total= 0
let sortedArray = ar.sort((cur,next)=>{
    return cur<next
})

ar.map(item => {
    if(item===sortedArray[0]) {
        total ++;
    }
    })
return total
}

So I sorted the given array and then map through the array and check how many of the numbers are equal to the maximum number in that array and count the total.

This will pass 8/9 test cases, one of the test cases, have a array with length of 100000 and for this one it failed, this is the given data for this test case.

Really can't get it why it fails in this test, is it possible that this happened because of JavaScript which is always synchronous and single-threaded?

I tried to use Promise and async await, but hackerrank will consider the first return as the output ( Which is the Promise itself ) and it not use the resolve value as a output, so can't really test this.

Is it something wrong with my logic?

Upvotes: 1

Views: 88

Answers (2)

Noor A Shuvo
Noor A Shuvo

Reputation: 2807

In your case, the build in function sort is using the resource heavily. Maybe that's the reason it is failing for a space/time complexity.

BTW, This problem can be solved easily using a for loop. The idea is

Pseudocode

var maxNum = -999999; // put here the highest limit of int or what ever data type 
int count = 0;
for(x in arr)
{
  if (x > maxNum)
  {
     maxNum = x;
     count = 1;
  }

  if(x==maxNum) count ++;
}

Here count will be the output.

The full code is 

function birthdayCakeCandles(ar) {
  var maxNum = -1;
  var count = 0;

   for(var i=0; i< ar.length; i++){
       var x = ar[i];

       if(x<maxNum) continue;

       if(x>maxNum){
           maxNum = x;
           count = 1;
       }       
       else{
        count++;
       }       
   }
return count;
}

Upvotes: 2

ggorlen
ggorlen

Reputation: 57135

The sorting approach is too slow (O(n log n) time complexity). For algorithmic challenges on HR, it's unlikely that features somewhat particular to your language choice like promises/async are going to rescue you.

You can do this in one pass using an object to keep track of how many times you've "seen" each number and the array's maximum number, then simply index into the object to get your answer:

function birthdayCakeCandles(ar) {
    let best = -Infinity;
    const seen = {};

    for (let i = 0; i < ar.length; i++) {
        if (ar[i] > best) {
            best = ar[i];
        }

        seen[ar[i]] = ++seen[ar[i]] || 1;
    }

    return seen[best];
}

Time and space complexity: O(n).

Edit:

This answer is even better, with constant space (here it is in JS):

function birthdayCakeCandles(ar) {
    let best = -Infinity;
    let count = 0;

    for (const n of ar) {
        if (n > best) {
            best = n;
            count = 1;
        }
        else if (n === best) {
            count++;
        }
    }

    return count;
}

Upvotes: 5

Related Questions