Toggle Light Bulbs

Difficulty: Easy | Acceptance: 71.90% | Paid: No Topics: Array, Hash Table, Sorting, Simulation

There are n light bulbs labeled from 1 to n. Initially, all bulbs are off.

You are given an array operations where operations[i] represents the index of the bulb to toggle in the i-th operation.

Toggling a bulb means changing its state from off to on, or from on to off.

Return the number of bulbs that are on after performing all operations.

• Examples
• Constraints
• Approach 1: Simulation
• Approach 2: Hash Map Frequency Count
• Approach 3: Sorting and Grouping

Examples

Example 1:

Input: n = 3, operations = [2, 1, 3, 2]
Output: 2
Explanation: 
- Operation 1: Toggle bulb 2. State: [0, 1, 0]
- Operation 2: Toggle bulb 1. State: [1, 1, 0]
- Operation 3: Toggle bulb 3. State: [1, 1, 1]
- Operation 4: Toggle bulb 2. State: [1, 0, 1]
Bulbs 1 and 3 are on.

Example 2:

Input: n = 5, operations = [1, 2, 3, 4, 5]
Output: 5
Explanation: Each bulb is toggled exactly once, so all bulbs are on.

Constraints

1 <= n <= 10⁴
1 <= operations.length <= 10⁴
1 <= operations[i] <= n

Approach 1: Simulation

Intuition Directly simulate the process using an array to represent the state of each bulb. Iterate through the operations and flip the state of the corresponding bulb.

Steps

• Initialize an array bulbs of size n with all values set to 0 (off).
• Iterate through each index op in the operations array.
• Toggle the state of the bulb at index op - 1 (0-indexed) by flipping 0 to 1 or 1 to 0.
• After processing all operations, count the number of 1s in the bulbs array and return it.

Complexity

• Time: O(n + m), where m is the length of operations.
• Space: O(n) to store the bulb states.
• Notes: Simple and intuitive, but uses extra space proportional to n.

Approach 2: Hash Map Frequency Count

Intuition A bulb ends up being on if it is toggled an odd number of times. Instead of tracking the state, we can count how many times each bulb index appears in the operations array.

Steps

• Create a hash map (or dictionary) to store the frequency of each bulb index.
• Iterate through the operations array and increment the count for the current index.
• Iterate through the hash map. For each entry, if the count is odd, increment the result.
• Return the result.

Complexity

• Time: O(m) on average to build the map and iterate.
• Space: O(n) in the worst case to store frequencies.
• Notes: Efficient if operations are sparse, but uses O(n) space.

Approach 3: Sorting and Grouping

Intuition If we sort the operations, identical operations will be adjacent. Two identical operations cancel each other out (even count). We can iterate through the sorted list and toggle state only when the current operation differs from the previous one.

Steps

• Sort the operations array.
• Initialize result = 0 and i = 0.
• Iterate through the sorted operations using a while loop or pointer.
• For each unique value in the sorted array, count how many times it appears consecutively.
• If the count is odd, increment result.
• Move the pointer to the next unique value.
• Return result.

Complexity

• Time: O(m log m) due to sorting.
• Space: O(1) or O(m) depending on the sorting algorithm’s space complexity.
• Notes: Useful if the input is unsorted and we want to avoid hash table overhead, but generally slower than Hash Map due to sorting.