Toggle Light Bulbs - Video Solutions
3842. Toggle Light Bulbs (Leetcode Easy)
Toggle Light Bulbs - Video Solution
Watch 10 video solutions for Toggle Light Bulbs, a easy level problem involving Array, Hash Table, Sorting. This walkthrough by Programming Live with Larry has 201 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 initially.
For each element bulbs[i] in the array bulbs:
- If the
bulbs[i]thlight bulb is currently off, switch it on. - Otherwise, switch it off.
Return the list of integers denoting the light bulbs that are on in the end, sorted in ascending order. If no bulb is on, return an empty list.
Example 1:
Input: bulbs = [10,30,20,10]
Output: [20,30]
Explanation:
- The
bulbs[0] = 10thlight bulb is currently off. We switch it on. - The
bulbs[1] = 30thlight bulb is currently off. We switch it on. - The
bulbs[2] = 20thlight bulb is currently off. We switch it on. - The
bulbs[3] = 10thlight bulb is currently on. We switch it off. - In the end, the 20th and the 30th light bulbs are on.
Example 2:
Input: bulbs = [100,100]
Output: []
Explanation:
- The
bulbs[0] = 100thlight bulb is currently off. We switch it on. - The
bulbs[1] = 100thlight bulb is currently on. We switch it off. - In the end, no light bulb is on.
Constraints:
1 <= bulbs.length <= 1001 <= bulbs[i] <= 100
Approach Overview
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.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation with Hash Set | O(n) | O(n) | Best general solution when toggles are processed sequentially |
| Frequency Counting + Sorting | O(n log n) | O(n) | Useful when you also need counts or when results must be returned in sorted order |