Toggle Light Bulbs - Solution & Explanation

Problem Overview: You receive a sequence of operations where specific light bulbs are toggled (on becomes off, off becomes on). After processing all operations, return the bulbs that remain on. Each toggle flips the current state, so the final state depends on whether a bulb was toggled an odd or even number of times.

Approach 1: Direct Simulation with Hash Set (O(n) time, O(n) space)

The most straightforward way to model toggling is with a HashSet. Iterate through the array of toggle operations. If a bulb ID is not in the set, add it (the bulb becomes on). If it already exists, remove it (the bulb turns off). This works because every toggle flips membership in the set. After processing all operations, the set contains exactly the bulbs toggled an odd number of times. Convert the set to a list and sort if the output must be ordered. This approach uses constant-time hash lookups and cleanly models the simulation.

Approach 2: Frequency Counting + Sorting (O(n log n) time, O(n) space)

Another way to simulate the process is by counting how many times each bulb appears. Use a HashMap or array frequency table where the key is the bulb index and the value is the number of toggles. Iterate through the input and increment the counter for each bulb. Afterward, iterate over the map and keep only bulbs with odd counts since an even number of toggles cancels out. If the result must be returned in order, collect those bulbs and sort them. This approach is conceptually simple and sometimes preferred when additional statistics about toggles are needed.

The problem is primarily a Array simulation task with constant-time lookups using a Hash Table. Sorting may be required depending on the output format, which introduces a Sorting step.

Recommended for interviews: The hash set simulation is the expected solution. It runs in O(n) time with O(n) space and clearly models the toggle behavior. Interviewers usually want to see you recognize that toggling twice cancels out, which naturally maps to inserting and removing from a set.