Problem Breakdown
We are given an array light representing a sequence of bulb activations over time (moments). The bulbs are numbered from 1 to n, where n is the length of the input array. At each moment k, we turn on the specific bulb indicated by light[k].
A bulb turns blue if it is currently ON and all bulbs with smaller IDs than itself have also been turned on (i.e., there are no gaps in the set of active bulbs starting from 1). We need to count how many moments exist where all currently turned-on bulbs satisfy this “blue” condition.
- Inputs: An array
lightcontaining a permutation of numbers from 1 to n. - Outputs: An integer representing the number of valid moments (indices) in the sequence.
- Implicit Constraints: The input is guaranteed to be a unique permutation, so we don’t need to handle duplicates or missing values outside the range [1, n].
- Edge Cases:
n = 1: Always returns 1 because the single bulb turns on and satisfies the condition immediately.- Sorted input
[1, 2, ..., n]: Every moment is valid (returns n). - Reverse sorted or random permutations: We need to track when gaps are filled up to the current maximum ID seen so far.
Intuition
A naive approach would be to maintain a set of active bulbs at each step and check if every bulb in that set has all smaller IDs present as well. Checking this condition for every moment takes per moment, leading to an overall complexity of . Given the constraint n <= 5 * 10^4, we need a linear solution.
Key Insight:
Since the input is a permutation of unique integers from 1 to n:
At any given step (moment), let’s say we have processed k bulbs so far (where k = index + 1). If the largest bulb ID seen among these k active bulbs equals k, then it implies that all numbers from 1 up to max_seen are present. Why? Because if any number between 1 and max_seen were missing, we would have fewer than max_seen unique elements processed so far (since duplicates aren’t allowed).
Therefore, the condition “all turned on bulbs are blue” is satisfied at moment k if and only if:
(number of active bulbs) == (maximum bulb ID seen so far)
Since (number of active bulbs) simply equals the current loop index + 1 in a single pass iteration, we just need to check if current_index + 1 == max_val_seen.
Approach
We iterate through the light array once. We maintain two variables:
max_val: Tracks the highest bulb ID encountered so far.ans: Counts how many times the condition is met.
For each element in the loop (let’s say at index i, value x):
- Update
max_val = max(max_val, x). - Check if
(i + 1) == max_val. If true, it means we have successfully turned on all bulbs from 1 tomax_valwithout gaps. Incrementans.
This works because the input is a permutation of unique values; thus, having processed exactly k items with a maximum value of k guarantees that those k items are specifically {1, ..., k}.
Complexity Analysis
- Time Complexity: where N is the length of
light. We iterate through the array once performing constant time operations inside the loop. - Space Complexity: . We only use a few integer variables (
max_val,ans) regardless of input size.
Solution
class Solution:
def numTimesAllBlue(self, light: List[int]) -> int:
max_seen = 0
ans = 0
for i in range(len(light)):
# Update the maximum bulb ID seen so far
current_bulb = light[i]
if current_bulb > max_seen:
max_seen = current_bulb
# If we have processed (i + 1) bulbs and the largest one is exactly that count,
# it implies all numbers from 1 to max_seen are present.
if i + 1 == max_seen:
ans += 1
return ans
Edge Cases Handled
- Single Element (
n=1): The loop runs once,max_seenbecomes 1, check passes (), returns 1. Correct. - Already Sorted: Every step satisfies the condition because we fill sequentially. Returns n.
- Gaps Filled Later (e.g.,
[2, 1]):- i=0, val=2: max=2, count=1 (). No increment.
- i=1, val=1: max=2, count=2 (). Increment. Returns 1. Correct (only moment when both are on is valid).