Domain 2MediumMEDIUM

Bulb Switcher IV

LeetCode problem 1529: Bulb Switcher IV (medium).

Domain: medium•Updated: 2026-09-17
#String

Problem Breakdown

We are given a binary string representing the desired state of nn bulbs (target), where ‘1’ is ON and ‘0’ is OFF. Initially, all bulbs are OFF (“0”). We can perform an operation: choose index i, and flip (toggle) every bulb from i to n-1. The goal is to find the minimum number of operations required to transform “0…0” into target.

  • Inputs: A string target containing only ‘0’ or ‘1’.
  • Output: An integer representing the minimum flip count.
  • Implicit Constraints: Operations are suffix flips (indices ii through end). This means an operation at index jj does not affect any bulb with index <j< j.
  • Edge Cases:
    • target consisting entirely of ‘0’s: Requires 0 operations.
    • target starting with ‘1’: Requires a flip immediately to turn the first bulb on (and potentially others).

Intuition

A brute-force approach using BFS or recursion would explore 2n2^n states, which is infeasible for n=105n=10^5. We need an observation about how operations propagate.

Since every operation at index i affects all indices ≥i\ge i, but leaves indices <i< i untouched, we can process the string from left to right (index 0 to n-1). When standing at index i, the state of bulb i is determined by how many times it has been flipped by operations starting before or exactly at i. Operations starting after i do not affect bulb i.

Therefore, if we encounter a mismatch between our current simulated state and target[i], we must perform an operation starting exactly at i to correct the value of this specific bulb without disturbing any previous bulbs (which are already matched). This suggests a greedy strategy: iterate left-to-right, track the effective “current” state based on accumulated flips, and increment our flip counter whenever the current target character differs from that expected state.

Approach

  1. Initialize flips = 0 to count operations.
  2. Maintain a variable state, initialized to ‘0’ (representing all bulbs are initially OFF). This tracks what value bulb ii currently has based on previous flips.
  3. Iterate through each character in target:
    • If the current target character matches state (‘1’ or ‘0’), continue without action. The flip count remains unchanged, and we move to the next index (the operation at this step would have been unnecessary).
    • If there is a mismatch (target[i] != state), it means bulb ii needs its value toggled relative to previous operations. Since no future operation can fix bulb ii, we must perform an operation starting here.
      • Increment flips.
      • Toggle the state variable (since this new flip affects all subsequent bulbs).
  4. Return flips.

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the length of target. We iterate through the string exactly once with constant-time operations inside the loop.
  • Space Complexity: O(1)O(1). We only use a few integer/character variables for state tracking regardless of input size.

Solution

def min_flips(target: str) -> int:
    flips = 0
    # 'state' tracks the current effective value (0 or 1) 
    # considering all operations performed so far on indices <= i.
    # Initially, no bulbs are flipped, so state is '0'.
    current_state = '0' 
    
    for char in target:
        if char != current_state:
            flips += 1
            # Perform a flip starting at this index; 
            # it toggles the effective value seen by all subsequent indices.
            current_state = '1' if current_state == '0' else '0'
            
    return flips

# Example usage for verification (not part of submission)
# print(min_flips("10111"))  # Output: 3

Edge Cases Handled

  • All Zeros: The loop runs, char always equals current_state (‘0’), so flips remains 0. Correct.
  • Alternating Pattern (e.g., “10”):
    • i=0 (‘1’): Mismatch with ‘0’. Flip count becomes 1, state toggles to ‘1’.
    • i=1 (‘0’): Match? No, target is ‘0’, current_state is now ‘1’ due to previous flip. Wait… logic check:
      • If target=“10”. Init state=‘0’.
      • Char ‘1’: Mismatch with ‘0’. Flip -> count=1, state becomes ‘1’.
      • Char ‘0’: Target is ‘0’, State is ‘1’. Mismatch. Flip -> count=2, state becomes ‘0’.
      • Wait, Example 4 logic check again? “10”. Start “00”. Op at 0 (“11”). Op at 1 (“10”). Total 2 flips. Correct.
  • Single Character: Handled correctly by the loop structure (either matches or mismatches immediately).