CODEWITHSUNDEEP
javascriptarrays
Aryamaan Goswamy
Aryamaan Goswamy

Reputation: 319

A faster solution for long inputs?

Let's say I have this problem:

https://www.hackerrank.com/challenges/birthday-cake-candles/problem

And I whip up this solution:

function bcc(arr) {
    let res = 0;
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] == Math.max(...arr)) {
            res++;
        }
    }
    return res;
}

console.log(bcc([4, 4, 3, 1]));

Now, for an array like [4, 4, 3, 1] it works fine. But HackerRank just gave me this huge array with 100,000 elements and the expected output is 7147. My code timed out and I got 5/9 problems wrong.

Can you give me a faster solution that I could use, maybe for other problems too?

Upvotes: 1

Views: 72

Answers (2)

Christopher Schneider
Christopher Schneider

Reputation: 3915

The issue with your solution is, as the other answer said, it's O(n^2). As for why that is, you calculate the max every time you go through the loop instead of just once. That is because Math.max has to go through the entire array to find the maximum value and you call it on every iteration of the loop.

Calculating the max value in the beginning isn't ideal either, though it works. You can just calculate it as you go. It's O(n) instead of O(2n) which still comes to O(n) but is more efficient.

function birthdayCakeCandles(ar) {
    var max = 0;
    var candleCount = 0;
    for(var i = 0; i < ar.length; i++) {
        if(ar[i] > max) {
            max = ar[i];
            candleCount = 1;
        } else if (ar[i] === max) {
            candleCount++;
        }
    }
    return candleCount;
}

With this solution, you only iterate the array once instead of twice. If you encounter a new maximum value, you simply reset candleCount and start counting again.

Upvotes: 1

CertainPerformance
CertainPerformance

Reputation: 370879

Calculate the maximum value of the array in advance, not on every iteration, and use reduce for brevity:

function birthdayCakeCandles(ar) {
  const max = Math.max(...ar);
  return ar.reduce((a, b) => a + (b === max), 0);
}

This reduces the overall computational complexity from O(n ^ 2) to O(n).

Or, closer to your original code:

function birthdayCakeCandles(arr) {
  const max = Math.max(...arr);
  let res = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] == max) {
      res++;
    }
  }
  return res;
}

Upvotes: 3

Related Questions