Leetcode 1375. Bulb Switcher III

Problem Explanation

The problem deals with a room full of light bulbs that are being turned on one by one. A light bulb turning on can be thought of as a moment. Initially all bulbs are off. The bulbs in the room are turned on and change their color to blue only if all the previous bulbs to its left are turned on.

Our task is to determine the number of moments when all the bulbs that are turned on are blue.


Approach

Given the nature of the problem, an efficient way to solve this problem would be to keep track of the rightmost bulb that has been turned on. This is because the blue condition (all previous bulbs being turned on) can only be affected by bulbs to the right of the current bulb.

As we traverse through the list of moments (from 0 to n-1), we continuously update the rightmost bulb. If at any moment, the rightmost bulb matches the value of i + 1 (i being the current index) this means that all bulbs from 1 to i+1 are turned on (i.e they are a permutation of light[0...i]), then increment the count of moments by 1, as all turned-on bulbs are blue.

Then, return the number of moments.


Walkthrough

Let's consider the example light = [2,1,4,3,6,5]

  • At moment 0, rightmost light = 2, 2 != 0 + 1, so the count stays at 0.
  • At moment 1, rightmost light = 2, 2 == 1 + 1, so the count increments to 1.
  • At moment 2, rightmost light = 4, 4 != 2 + 1, so the count stays at 1.
  • At moment 3, rightmost light = 4, 4 == 3 + 1, so the count increments to 2.
  • At moment 4, rightmost light = 6, 6 != 4 + 1, so the count stays at 2.
  • At moment 5, rightmost light = 6, 6 == 5 + 1, so the count increments to 3.

So, the output for this example is 3.


C++ Solution

1
2C++
3class Solution {
4 public:
5  int numTimesAllBlue(vector<int>& flips) {
6    int ans = 0; // Initialize count of moments
7    int rightmost = 0; // Initialize rightmost light bulb
8    
9    // Traverse the array
10    for (int i = 0; i < flips.size(); ++i) {
11      // Update the rightmost light bulb
12      rightmost = max(rightmost, flips[i]);
13      
14      // Check if max(flips[0..i]) = i + 1, which means all bulbs are ON
15      if (rightmost == i + 1)
16        // Increment count of moments
17        ++ans;
18    }
19    // Return count of moments
20    return ans;
21  }
22};

The solution can be implemented in much the same way in other languages.# Python Solution

The Python solution follows the same logic as the previously described solution:

1
2python
3class Solution:
4    def numTimesAllBlue(self, light):
5        max_right = ans = 0
6        for i in range(len(light)):
7            max_right = max(max_right, light[i])
8            if max_right == i + 1:
9                ans += 1
10        return ans

JavaScript Solution

The Javascript solution also follows the same concept:

1
2javascript
3var numTimesAllBlue = function(light) {
4    let max_right = 0, ans = 0
5    for(let i = 0; i < light.length; i++){
6        max_right = Math.max(max_right, light[i])
7        if(max_right == i + 1)
8            ans++;
9    }
10    return ans
11};

Java Solution

The JavaSolution is implemented a bit differently due to the language’s syntax:

1
2java
3class Solution {
4    public int numTimesAllBlue(int[] light) {
5        int rightmost = 0, ans = 0;
6        for (int i = 0; i < light.length; ++i) {
7            rightmost = Math.max(rightmost, light[i]);
8            if (rightmost == i + 1)
9                ans++;
10        }
11        return ans;
12    }
13}

With the presented solutions above in C++, Python, JavaScript, and Java, you should be able to solve the problem regardless of the preferred programming language. Keep practicing such concepts to enhance your problem-solving skills.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫