[Hackerrank] – Birthday Cake Candles Solution

nikoo28

4 years ago

Question: You need to count the number of tallest candles on the cake.
Input: candles = [4, 4, 1, 3]
Output: 2

Let us try to understand the problem statement and its test case first.

You are in charge of candles on a birthday cake for a child. However, the child can only blow out the tallest candles. There could be one or more candles on the cake that are tallest. Hence, you need to return the number of tallest candles you can find.

Let us take a sample test case. candles[ ] = [3, 2, 1, 3]. Here the integers in the array represent the height of each of the candle. They are placed on the cake something like the image shown below.

You can see that some candles are small and some are large. If you look closely, the tallest candle available here is of the length 3 and there are 2 of such candles. According to the question, when you blow out, only the tallest candles extinguish. If you blow, your cake looks like this now.

In this test case, 2 candles are blown out. Hence, 2 is the answer.

Method 1:

This is a very simple problem to solve, if you don’t apply too much complications. A very basic algorithm will be something like:

Iterate through the array and find the length of the tallest candle.
Store this length.
Go over the array once again and check if the candle matches the maximum length.
If yes, increment a result counter. Else, continue to the next candle.
Return the result.

Quite a straight forward approach. Let us assume that we have a sample array:
candles[] = [4, 1, 1, 4, 3, 4]

This can represent the birthday cake candles:

On doing one iteration, we find that the largest value in the array is 4. In the next iteration, we compare each value in the array to the maximum value and if they match, increment a counter. At the end, we get the total number of blown out candles to be 3.

Code:

  int birthdayCakeCandles(List<Integer> candles) {

    int maximum = Integer.MIN_VALUE;

    // Get the height of the tallest candle
    for (Integer candle : candles) {
      if (candle >= maximum)
        maximum = candle;
    }

    // Count how many tallest candles are present
    int result = 0;
    for (Integer candle : candles) {
      if (candle == maximum)
        result++;
    }

    return result;
  }
Code language: Java (java)

Time Complexity: $O(n)$
Space Complexity: $O(1)$

Method 2: Using single iteration (stream of numbers)

You don’t really need to scan the array 2 times, to determine the tallest birthday cake candles. This problem can be actually converted to determine the count of largest numbers in a stream of integers.

The basic algorithm would be:

Consider first number to be the largest number and set counter = 1.
If the next number is smaller than the largest number, continue.
If the next number is same as the largest number, increment the counter by 1
However, if the next number is larger than the largest number, reset the counter to 1, and change the largest number to this new number.
Keep repeating the above 3 steps until you are getting a stream of numbers.
Return the counter at the end.

Code:

  int birthdayCakeCandlesStream(List<Integer> candles) {

    int maximum = Integer.MIN_VALUE;
    int result = 0;

    for (Integer candle : candles) {
      if (candle < maximum)
        continue;
      if (candle == maximum)
        result++;
      if (candle > maximum) {
        result = 1;
        maximum = candle;
      }
    }

    return result;
  }
Code language: Java (java)

Method 1:

Code:

Method 2: Using single iteration (stream of numbers)

Code:

Video Explanation: