1375. Bulb Switcher III

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]

Rust Solution

struct Solution;

impl Solution {
    fn num_times_all_blue(light: Vec<i32>) -> i32 {
        let n = light.len();
        let mut res = 0;
        let mut max = std::usize::MIN;
        for i in 0..n {
            max = max.max((light[i] - 1) as usize);
            if max == i {
                res += 1;
            }
        }
        res
    }
}

#[test]
fn test() {
    let light = vec![2, 1, 3, 5, 4];
    let res = 3;
    assert_eq!(Solution::num_times_all_blue(light), res);
    let light = vec![3, 2, 4, 1, 5];
    let res = 2;
    assert_eq!(Solution::num_times_all_blue(light), res);
    let light = vec![4, 1, 2, 3];
    let res = 1;
    assert_eq!(Solution::num_times_all_blue(light), res);
    let light = vec![2, 1, 4, 3, 6, 5];
    let res = 3;
    assert_eq!(Solution::num_times_all_blue(light), res);
    let light = vec![1, 2, 3, 4, 5, 6];
    let res = 6;
    assert_eq!(Solution::num_times_all_blue(light), res);
}

Having problems with this solution? Click here to submit an issue on github.