3842. Toggle Light Bulbs

EasyArrayHash TableSortingSimulation

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given an array bulbs of integers between 1 and 100.

There are 100 light bulbs numbered from 1 to 100. All of them are switched off at the start.

For each element bulbs[i] in the array bulbs, you need to perform a toggle operation:

If the bulbs[i]-th light bulb is currently off, switch it on.
Otherwise (the bulb is currently on), switch it off.

In other words, every time a bulb's number appears in the array, its state flips. A bulb that is toggled an odd number of times will end up on, while a bulb toggled an even number of times will end up off.

After processing every element in bulbs, return the list of integers representing the light bulbs that are on in the end, sorted in ascending order. If no bulb is on, return an empty list.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Direct simulation of bulb toggling using a fixed-size state array.

Open in Flowchart

Intuition

The key observation is that each bulb only has two possible states: on or off. Every time a bulb's number appears in the array, its state flips. This means we only care about how many times each bulb is toggled — specifically, whether that count is odd or even.

If a bulb is toggled an odd number of times, it ends up on.
If a bulb is toggled an even number of times, it ends up off.

This "flip back and forth" behavior is exactly what the XOR operation captures. Starting from 0 (off), applying ^= 1 repeatedly cycles the value between 0 and 1: 0 → 1 → 0 → 1 → .... So instead of counting toggles, we can directly maintain each bulb's current state and flip it with XOR each time we see its number.

Since the bulb numbers are limited to the range 1 to 100, we can use a small fixed-size array st to track the state of every bulb. We simply walk through the input, flip the corresponding entry for each number, and at the end collect all indices whose value is 1 — these are the bulbs that remain on. Because we scan the array in index order, the result is naturally produced in ascending order.

Pattern Learn more about Sorting patterns.

Solution Approach

Solution 1: Simulation

We use an array st of length 101 to record the state of each light bulb. Initially, all elements are 0, indicating that all light bulbs are in the off state. We deliberately make the length 101 (instead of 100) so that we can index bulbs directly by their number from 1 to 100, ignoring index 0.

The steps are as follows:

Initialize the state array: Create st = [0] * 101, where st[i] represents the current state of bulb i (0 for off, 1 for on).
Process each toggle: For each element x in the array bulbs, we toggle the value of st[x] using the XOR operation st[x] ^= 1. This flips the state: 0 becomes 1, and 1 becomes 0. After processing the entire array, each st[x] holds the final state of bulb x, which depends on whether x appeared an odd or even number of times.
Collect the result: We traverse the st array and gather all indices i whose value is 1 into the result list. This is done with the list comprehension [i for i, x in enumerate(st) if x]. Since enumerate visits indices in increasing order, the resulting list is automatically sorted in ascending order.

The time complexity is O(n + M), where n is the length of the array bulbs and M = 100 is the number of bulbs. The space complexity is O(M) for the state array st.

Example Walkthrough

Let's trace through the solution with a small example: bulbs = [3, 1, 3, 5, 1, 3].

We start with the state array st (showing only the relevant indices 1 through 5, all initialized to 0):

Bulb	1	2	3	4	5
State	0	0	0	0	0

Now we process each element in bulbs, applying st[x] ^= 1:

Step 1 — x = 3: Bulb 3 is off (0), flip it on. st[3] becomes 1.

Bulb	1	2	3	4	5
State	0	0	1	0	0

Step 2 — x = 1: Bulb 1 is off (0), flip it on. st[1] becomes 1.

Bulb	1	2	3	4	5
State	1	0	1	0	0

Step 3 — x = 3: Bulb 3 is on (1), flip it off. st[3] becomes 0.

Bulb	1	2	3	4	5
State	1	0	0	0	0

Step 4 — x = 5: Bulb 5 is off (0), flip it on. st[5] becomes 1.

Bulb	1	2	3	4	5
State	1	0	0	0	1

Step 5 — x = 1: Bulb 1 is on (1), flip it off. st[1] becomes 0.

Bulb	1	2	3	4	5
State	0	0	0	0	1

Step 6 — x = 3: Bulb 3 is off (0), flip it on. st[3] becomes 1.

Bulb	1	2	3	4	5
State	0	0	1	0	1

Collecting the result: We scan st from left to right and pick every index whose value is 1. Here, bulbs 3 and 5 are on.

Let's verify against the toggle counts:

Bulb 1 appears 2 times (even) → off ✓
Bulb 3 appears 3 times (odd) → on ✓
Bulb 5 appears 1 time (odd) → on ✓

Since we visit indices in increasing order via enumerate, the output comes out naturally sorted:

Final answer: [3, 5]

Solution Implementation

1class Solution:
2    def toggleLightBulbs(self, bulbs: list[int]) -> list[int]:
3        # Track the on/off state of each bulb index (0 = off, 1 = on).
4        # Size 101 covers bulb indices in the range [0, 100].
5        bulb_states = [0] * 101
6
7        # Each occurrence of an index toggles that bulb's state.
8        for index in bulbs:
9            bulb_states[index] ^= 1
10
11        # Collect indices whose final state is "on" (value 1).
12        return [index for index, state in enumerate(bulb_states) if state]
13

1class Solution {
2    /**
3     * Toggles light bulbs based on the given list of bulb indices.
4     * Each time a bulb's index appears, its state is flipped (on/off).
5     * Returns the indices of all bulbs that end up in the "on" state.
6     *
7     * @param bulbs the list of bulb indices to toggle
8     * @return a list of indices whose bulbs are switched on
9     */
10    public List<Integer> toggleLightBulbs(List<Integer> bulbs) {
11        // state[i] represents the on/off status of bulb i (0 = off, 1 = on).
12        // Index range is fixed to [0, 100], hence size 101.
13        int[] state = new int[101];
14
15        // Flip the state for every occurrence of a bulb index.
16        // XOR with 1 toggles between 0 and 1.
17        for (int index : bulbs) {
18            state[index] ^= 1;
19        }
20
21        // Collect all bulb indices that are currently switched on.
22        List<Integer> result = new ArrayList<>();
23        for (int i = 0; i < state.length; ++i) {
24            if (state[i] == 1) {
25                result.add(i);
26            }
27        }
28
29        return result;
30    }
31}
32

1class Solution {
2public:
3    vector<int> toggleLightBulbs(vector<int>& bulbs) {
4        // Track the on/off state for each bulb index (0 = off, 1 = on).
5        // Size 101 assumes bulb indices fall within the range [0, 100].
6        vector<int> state(101, 0);
7
8        // Toggle the state for every bulb index encountered.
9        // XOR with 1 flips the state: off -> on, on -> off.
10        for (int bulb : bulbs) {
11            state[bulb] ^= 1;
12        }
13
14        // Collect all indices whose final state is "on".
15        vector<int> result;
16        for (int i = 0; i < 101; ++i) {
17            if (state[i]) {
18                result.push_back(i);
19            }
20        }
21
22        return result;
23    }
24};
25

1/**
2 * Toggles light bulbs based on the given positions and returns the indices
3 * of the bulbs that remain in the "on" state.
4 *
5 * Each occurrence of a bulb index in the input flips that bulb's state
6 * (on -> off, off -> on). After processing all toggles, the indices of
7 * bulbs that are on are collected in ascending order.
8 *
9 * @param bulbs - An array of bulb indices to toggle (each in range [0, 100]).
10 * @returns An array of indices for bulbs that are in the "on" state.
11 */
12function toggleLightBulbs(bulbs: number[]): number[] {
13    // Maximum number of bulb positions supported (indices 0..100).
14    const maxBulbs = 101;
15
16    // state[i] holds the on/off status of bulb i (0 = off, 1 = on).
17    const state: number[] = new Array(maxBulbs).fill(0);
18
19    // Flip the state of each bulb for every occurrence in the input.
20    for (const index of bulbs) {
21        state[index] ^= 1;
22    }
23
24    // Collect indices of all bulbs that are currently on.
25    const result: number[] = [];
26    for (let i = 0; i < maxBulbs; i++) {
27        if (state[i] === 1) {
28            result.push(i);
29        }
30    }
31
32    return result;
33}
34

Time and Space Complexity

Time Complexity: O(n), where n is the length of the array bulbs. The first loop iterates over each element of bulbs to toggle the corresponding state, taking O(n) time. The final list comprehension iterates over the fixed-size array st of length 101, contributing a constant O(101) time. Therefore, the overall time complexity is dominated by O(n).
Space Complexity: O(M), where M is the maximum bulb number. The auxiliary array st has a fixed size that must accommodate the largest bulb index, requiring O(M) space (here capped at 101). The output list is not counted as extra space.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Using a fixed-size array of length 100 with 0-based indexing

A frequent mistake is to allocate the state array with length 100 and then index it directly with the bulb number:

bulb_states = [0] * 100   # indices 0..99
for index in bulbs:
    bulb_states[index] ^= 1   # IndexError when index == 100!

Since bulbs are numbered from 1 to 100, the value 100 is a valid input. With an array of length 100, the highest valid index is 99, so toggling bulb 100 raises an IndexError: list index out of range.

Solution: Allocate the array with length 101 so that index 100 is valid, and simply ignore index 0. This lets you map each bulb number directly to its array slot without any offset arithmetic:

bulb_states = [0] * 101   # indices 0..100, index 0 is unused
for index in bulbs:
    bulb_states[index] ^= 1   # safe for index in [1, 100]

Pitfall 2: Manually offsetting indices and forgetting to convert back

If you instead choose a length-100 array and offset every bulb by -1 to save one slot, it's easy to forget to convert the indices back to bulb numbers when building the result:

bulb_states = [0] * 100
for index in bulbs:
    bulb_states[index - 1] ^= 1

# Wrong: returns 0-based indices, not bulb numbers
return [i for i, s in enumerate(bulb_states) if s]

This returns values shifted by one (e.g., bulb 5 would appear as 4), producing incorrect output.

Solution: If you use the offset approach, remember to add 1 back when collecting results:

return [i + 1 for i, s in enumerate(bulb_states) if s]

Using the length-101 array (Pitfall 1's fix) avoids this entire class of off-by-one errors, since indices and bulb numbers line up naturally.

Pitfall 3: Assuming the result needs an explicit sort

Some implementations collect "on" bulbs into a set or dictionary first and then sort at the end:

on_bulbs = {index for index in bulbs if ...}
return sorted(on_bulbs)   # extra O(k log k) work

While correct, this is unnecessary. Because enumerate traverses the state array in increasing index order, the result is already sorted in ascending order. Adding an explicit sorted() call wastes time and signals a misunderstanding of why the approach works.

Solution: Trust the natural ordering of the state-array traversal and skip the redundant sort:

return [index for index, state in enumerate(bulb_states) if state]

This keeps the result-building step at O(M) instead of O(M log M).

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering