Skip to main content
Talentd

Toggle Light Bulbs - Solution & Explanation

EasyArrayHash TableSortingSimulation7 min readAsked at: Juspay
Practice this problem

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]th light 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] = 10th light bulb is currently off. We switch it on.
  • The bulbs[1] = 30th light bulb is currently off. We switch it on.
  • The bulbs[2] = 20th light bulb is currently off. We switch it on.
  • The bulbs[3] = 10th light 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] = 100th light bulb is currently off. We switch it on.
  • The bulbs[1] = 100th light bulb is currently on. We switch it off.
  • In the end, no light bulb is on.

 

Constraints:

  • 1 <= bulbs.length <= 100
  • 1 <= 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.

Solution

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. For each element bulbs[i] in the array bulbs, we toggle the value of st[bulbs[i]] (i.e., 0 becomes 1, and 1 becomes 0). Finally, we traverse the st array, add the indices with a value of 1 to the result list, and return the result.

The time complexity is O(n), where n is the length of the array bulbs. The space complexity is O(M), where M is the maximum bulb number.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Simulation with Hash SetO(n)O(n)Best general solution when toggles are processed sequentially
Frequency Counting + SortingO(n log n)O(n)Useful when you also need counts or when results must be returned in sorted order

Video Solution

3842. Toggle Light Bulbs (Leetcode Easy) • Programming Live with Larry • 201 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Toggle Light Bulbs easy or hard?
Toggle Light Bulbs is generally considered an easy problem. The key observation is that toggling the same bulb twice cancels out, so only bulbs toggled an odd number of times remain on. Once that insight is clear, a hash set simulation solves it efficiently.
Toggle Light Bulbs Python/Java solution
The typical implementation uses a set in Python or a HashSet in Java. For each bulb index in the toggle list, check membership and flip the state by inserting or removing it. This produces an O(n) solution with simple and readable code.
How to solve Toggle Light Bulbs in O(n)?
Use a hash set to track bulbs that are currently on. Iterate through the toggle list and flip membership in the set: add the bulb if it is not present, remove it if it already exists. After processing all operations, the remaining elements in the set represent bulbs toggled an odd number of times.
What is the best approach for Toggle Light Bulbs?
The hash set simulation approach is the most efficient. Iterate through each toggle operation and add the bulb to a set if it is off, or remove it if it is already on. This directly models the toggle behavior and runs in O(n) time with O(n) space.
Is Toggle Light Bulbs asked at Google/Amazon/Meta?
Array and hash-table simulation problems like Toggle Light Bulbs appear frequently in interviews at companies such as Amazon, Google, and Meta. The focus is usually on recognizing patterns like parity (odd vs even operations) and using constant-time hash lookups.
What data structure is used in Toggle Light Bulbs?
A hash set or hash map is the most common data structure. The set tracks which bulbs are currently on, while a map can count how many times each bulb was toggled. Arrays may also be used if the bulb range is small and known in advance.
What is the time complexity of Toggle Light Bulbs?
The optimal solution runs in O(n) time where n is the number of toggle operations. Each operation performs a constant-time hash lookup or removal. If the final list of bulbs needs to be sorted, the complexity becomes O(n log n).

Ready to solve this problem?

Practice Toggle Light Bulbs with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays