1375

1375. Bulb Switcher III (Medium)

There is a room with n bulbs, numbered from 1 to n, arranged in a row from left to right. Initially, all the bulbs are turned off.

At moment k (for k from 0 to n - 1), we turn on the light[k] bulb. A bulb change color to blue only if it is on and all the previous bulbs (to the left) are turned on too.

Return the number of moments in which all turned on bulbs are blue.

 

Example 1:

Input: light = [2,1,3,5,4]
Output: 3
Explanation: All bulbs turned on, are blue at the moment 1, 2 and 4.

Example 2:

Input: light = [3,2,4,1,5]
Output: 2
Explanation: All bulbs turned on, are blue at the moment 3, and 4 (index-0).

Example 3:

Input: light = [4,1,2,3]
Output: 1
Explanation: All bulbs turned on, are blue at the moment 3 (index-0).
Bulb 4th changes to blue at the moment 3.

Example 4:

Input: light = [2,1,4,3,6,5]
Output: 3

Example 5:

Input: light = [1,2,3,4,5,6]
Output: 6

 

Constraints:

• n == light.length
• 1 <= n <= 5 * 10^4
• light is a permutation of  [1, 2, ..., n]

Related Topics:
Array

Similar Questions:

• Bulb Switcher (Medium)
• Bulb Switcher II (Medium)

Solution 1. Brute Force

Try to turn the bulb from the current one as far as possible to blue. If the count of turned-on bulbs equals the count of blue bulbs, then increment the answer.

// OJ: https://leetcode.com/problems/bulb-switcher-iii/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(1)
class Solution {
public:
    int numTimesAllBlue(vector<int>& A) {
        int N = A.size(), ans = 0, on = 0, blue = 0;
        vector<int> v(N, 0);
        for (int n : A) {
            int i = n - 1;
            v[i] = 1;
            on++;
            while (i < N && v[i] > 0 && (i == 0 || v[i - 1] == 2)) {
                if (v[i] == 1) blue++;
                v[i++] = 2;
            } 
            if (on == blue) ++ans;
        }
        return ans;
    }
};

Solution 2.

What's the feature of the moments we care about? One is that the maximum ID we've seen equals the count of bulbs we've turned on.

// OJ: https://leetcode.com/problems/bulb-switcher-iii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int numTimesAllBlue(vector<int>& A) {
        int N = A.size(), maxId = 0, cnt = 0, ans = 0;
        for (int n : A) {
            maxId = max(maxId, n);
            if (++cnt == maxId) ++ans;
        }
        return ans;
    }
};