LeetCode 3842 - Toggle Light Bulbs

The problem gives us an array bulbs, where each value represents a light bulb number between 1 and 100. Initially, there are exactly 100 light bulbs, and every bulb is turned off. We process the array from left to right.

leetcodeeasyarrayhash-tablesortingsimulation

LeetCode Problem 3842

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Sorting, Simulation

Solution

LeetCode 3842 - Toggle Light Bulbs

Problem Understanding

The problem gives us an array bulbs, where each value represents a light bulb number between 1 and 100.

Initially, there are exactly 100 light bulbs, and every bulb is turned off.

We process the array from left to right. For each value bulbs[i]:

  • If that bulb is currently off, we turn it on.
  • If that bulb is currently on, we turn it off.

This operation is called a toggle because it flips the bulb's state every time it appears.

After processing every element in the array, we must return all bulb numbers that remain on. The output must be sorted in ascending order.

Another way to think about the problem is that every occurrence of a bulb number flips its state. A bulb that appears an odd number of times will end up on, while a bulb that appears an even number of times will end up off.

The constraints are very small:

  • 1 <= bulbs.length <= 100
  • 1 <= bulbs[i] <= 100

Since both the number of operations and the range of bulb numbers are limited to 100, almost any reasonable solution will run comfortably within the limits.

Important edge cases include repeated toggles of the same bulb, situations where every bulb is toggled an even number of times resulting in an empty answer, and cases where only a single bulb appears once and remains on. The problem guarantees that every bulb number is valid and lies between 1 and 100.

Approaches

Brute Force Approach

A straightforward approach is to explicitly maintain the state of all 100 bulbs.

We can create an array of size 101, where index i represents whether bulb i is on or off. Initially every value is False.

For each bulb number in the input, we flip its state. After processing all toggles, we scan through bulbs 1 through 100 and collect every bulb whose state is on.

This approach is correct because it directly simulates the behavior described in the problem statement.

Although this is already fast enough for the given constraints, it requires maintaining the state of every bulb even if only a few bulbs are actually touched.

Optimal Approach

The key observation is that we only care about bulbs whose state changes.

A hash set naturally represents the bulbs that are currently on:

  • If a bulb is not in the set, it is off.
  • If a bulb is in the set, it is on.

When processing a bulb number:

  • If it is already in the set, remove it because the bulb turns off.
  • Otherwise, add it because the bulb turns on.

At the end, the set contains exactly the bulbs that remain on. Since the output must be sorted, we simply return the sorted contents of the set.

This solution avoids tracking all 100 bulbs explicitly and stores only bulbs that are currently on.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n + 100) O(100) Simulates all bulb states using a fixed-size array
Optimal O(n + k log k) O(k) Uses a hash set of active bulbs, where k is the number of bulbs left on

Here, n is the length of bulbs and k is the number of bulbs that remain on after all toggles.

Algorithm Walkthrough

Optimal Algorithm

  1. Create an empty hash set called on_bulbs.

The set will store exactly the bulb numbers that are currently on. 2. Iterate through every bulb number in the input array.

For each bulb:

  • If the bulb already exists in on_bulbs, remove it.
  • Otherwise, add it.

This mirrors the toggle operation described in the problem. 3. After processing all values, the set contains exactly the bulbs that remain on. 4. Convert the set into a sorted list using ascending order. 5. Return the sorted list.

Why it works

The set maintains the invariant that it contains exactly the bulbs that are currently on.

Whenever a bulb number appears:

  • If the bulb is off, it is not in the set, so we add it.
  • If the bulb is on, it is in the set, so we remove it.

Thus every occurrence correctly flips the bulb's state. After all toggles are processed, the set contains precisely the bulbs that remain on. Sorting those values produces the required output.

Python Solution

class Solution:
    def toggleLightBulbs(self, bulbs: list[int]) -> list[int]:
        on_bulbs = set()

        for bulb in bulbs:
            if bulb in on_bulbs:
                on_bulbs.remove(bulb)
            else:
                on_bulbs.add(bulb)

        return sorted(on_bulbs)

The implementation begins by creating an empty set called on_bulbs. This set represents all bulbs that are currently on.

As we iterate through the input array, we perform the toggle operation. If the bulb already exists in the set, it is currently on, so we remove it. Otherwise, it is currently off, so we add it.

After all toggles have been processed, the set contains exactly the bulbs that remain on. Since the problem requires the answer to be sorted in ascending order, we return sorted(on_bulbs).

The code directly follows the algorithm described earlier and uses the constant-time membership operations provided by Python's hash set implementation.

Go Solution

func toggleLightBulbs(bulbs []int) []int {
	onBulbs := make(map[int]bool)

	for _, bulb := range bulbs {
		if onBulbs[bulb] {
			delete(onBulbs, bulb)
		} else {
			onBulbs[bulb] = true
		}
	}

	result := make([]int, 0, len(onBulbs))
	for bulb := range onBulbs {
		result = append(result, bulb)
	}

	sort.Ints(result)
	return result
}

The Go implementation uses a map as a hash set because Go does not provide a built-in set type.

A bulb is considered on if it exists in the map. Toggling is performed by inserting or deleting the bulb number. After processing all inputs, the remaining map keys are collected into a slice, sorted using sort.Ints, and returned.

Unlike Python, Go requires explicit sorting and explicit construction of the result slice. There are no integer overflow concerns because bulb numbers are limited to the range 1 to 100.

Worked Examples

Example 1

Input:

bulbs = [10, 30, 20, 10]
Step Current Bulb Set Before Action Set After
1 10 {} Add 10 {10}
2 30 {10} Add 30 {10, 30}
3 20 {10, 30} Add 20 {10, 20, 30}
4 10 {10, 20, 30} Remove 10 {20, 30}

Final set:

{20, 30}

Sorted result:

[20, 30]

Example 2

Input:

bulbs = [100, 100]
Step Current Bulb Set Before Action Set After
1 100 {} Add 100 {100}
2 100 {100} Remove 100 {}

Final set:

{}

Sorted result:

[]

Complexity Analysis

Measure Complexity Explanation
Time O(n + k log k) Each toggle is O(1) on average, then the remaining k bulbs are sorted
Space O(k) The set stores only bulbs that are currently on

The hash set operations, insertion, removal, and membership checks, all take constant time on average. After processing the input, we sort the bulbs that remain on. If k bulbs remain active, sorting requires O(k log k) time. The auxiliary space is proportional to the number of bulbs currently stored in the set.

Test Cases

solution = Solution()

assert solution.toggleLightBulbs([10, 30, 20, 10]) == [20, 30]  # provided example
assert solution.toggleLightBulbs([100, 100]) == []  # provided example

assert solution.toggleLightBulbs([1]) == [1]  # single bulb toggled once
assert solution.toggleLightBulbs([50, 50]) == []  # single bulb toggled twice
assert solution.toggleLightBulbs([1, 2, 3]) == [1, 2, 3]  # all remain on

assert solution.toggleLightBulbs([5, 5, 5]) == [5]  # odd number of toggles
assert solution.toggleLightBulbs([5, 5, 5, 5]) == []  # even number of toggles

assert solution.toggleLightBulbs([3, 1, 2]) == [1, 2, 3]  # output must be sorted

assert solution.toggleLightBulbs([100]) == [100]  # upper boundary bulb
assert solution.toggleLightBulbs([1, 100]) == [1, 100]  # boundary values together

assert solution.toggleLightBulbs(
    [1, 2, 3, 1, 2, 3]
) == []  # every bulb toggled an even number of times

assert solution.toggleLightBulbs(
    [1, 2, 3, 1, 2]
) == [3]  # only one bulb remains on

Test Summary

Test Why
[10, 30, 20, 10] Verifies the first provided example
[100, 100] Verifies the second provided example
[1] Smallest meaningful input
[50, 50] Even toggles cancel out
[1, 2, 3] Multiple bulbs remain on
[5, 5, 5] Odd toggle count leaves bulb on
[5, 5, 5, 5] Even toggle count leaves bulb off
[3, 1, 2] Confirms output sorting
[100] Tests upper bulb boundary
[1, 100] Tests both boundary values
[1, 2, 3, 1, 2, 3] All bulbs end off
[1, 2, 3, 1, 2] Exactly one bulb remains on

Edge Cases

A bulb is toggled an even number of times

Consider the input:

[7, 7]

A common mistake is to count appearances incorrectly and leave the bulb in the final answer. Since every occurrence flips the state, two toggles return the bulb to its original off state. The set-based implementation handles this naturally by adding the bulb on the first occurrence and removing it on the second.

A bulb is toggled an odd number of times

Consider:

[9, 9, 9]

After three toggles, the bulb should be on. This case verifies that the implementation does not simply track whether a bulb appeared, but correctly tracks its current state through repeated additions and removals. The final set contains 9, producing the correct result.

No bulbs remain on

Consider:

[1, 2, 1, 2]

Every bulb appears an even number of times, so all bulbs end up off. Some implementations may accidentally return None or an unsorted intermediate structure. The solution correctly returns an empty list because the final set is empty and sorted(set()) produces [].

Output ordering differs from processing order

Consider:

[30, 10, 20]

The bulbs are processed in a different order than the required output order. Since sets do not maintain sorted order, returning the set directly would be incorrect. The implementation explicitly sorts the remaining bulb numbers before returning them, guaranteeing ascending order as required by the problem statement.