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]

Accepted 25,281 Submissions 39,421

Note, given that at each moment we are turning a bulb on with no exception. Thus the following is true: for the bulbs are blue at the moment n, if and only if n lights are sequentially turned on from the left side.

This reduces the problem quite a bit, because we only need to keep track of how many bulbs are turned on left of the current index, as well as the index of the bulbs that are turned on right of the current index. We don’t need to keep track of left side, because the light array is a permutation – i.e. there are no repeating elements.

class Solution {
public:
    int numTimesAllBlue(vector<int>& light) {
        // Note, light array values are based in 1-index
        // we'll use 0-index
        uint64_t index = 0;

        // how many bulbs are on to the left side of index (inclusive)
        uint64_t left = 0;

        // Since we only track its presence
        // for non-existent keys, the default should be false
        // https://stackoverflow.com/questions/11058422/map-operator-and-bool-as-value
        std::map<int, bool> right;

        uint64_t blue = 0;

        for (std::vector<int>::iterator it = light.begin(); it != light.end(); ++it) {
            if (*it - 1<= index) {
                left++;
            }
            else {
                // keep track of index
                right[*it-1] = true;
            }
            
            // Increase all blue moment count
            // First, check if current index is in the right map
            if (right[index]) {
                right[index] = false;
                left++;
            }
            if (index + 1 == left) {
                blue++;
            }

            // increase current index
            index++;
        }
        return blue;
    }
};

After considerations and viewing some discussions, I realized that the problem could be further reduced. The map in the above code could be eliminated, because the only data we need to keep track of is the most right bulb index that is on. For example, if a bulb is turned on in the right side of the index, then there will not be any moments where the lights are blue unless all the lights leading up to that bulb is turned on.

class Solution {
public:
    int numTimesAllBlue(vector<int>& light) {
        // Note, light array values are based in 1-index
        // we'll use 0-index
        uint64_t index = 0;

        // how many bulbs are on to the left side of index (inclusive)
        uint64_t left = 0;

        uint64_t blue = 0;

        for (int i = 0; i < light.size(); i++) {
            if (light[i] - 1> left) {
                left = light[i] - 1;
            }

            // Increase all blue moment count
            if (index == left) {
                blue++;
            }

            // increase current index
            index++;
        }
        return blue;
    }
};