Abstract / Summary

Turn on certain lamps to light grid cells and determine which cells are illuminated after each operation.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 40% (70k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the illumination query problem on an n × n grid. It maintains four hash-maps that count active lamps on each row, column, and the two diagonal families. By converting the input lamp list into a set of unique coordinates, the algorithm guarantees that duplicate lamp specifications do not inflate the counters. For each query it checks the aggregated counts to decide whether the cell is illuminated, then proceeds to deactivate any lamp located in the 3 × 3 block centered on the query cell. The use of defaultdict(int) for the counters and a set for lamp positions enables constant-time updates and look-ups.

Data structures

The solution relies on four dictionaries that map a line identifier to the number of lamps currently illuminating that line:

horizontal = defaultdict(int)   # key: row index
vertical   = defaultdict(int)   # key: column index
diagonals1 = defaultdict(int)   # key: row - column (top-left to bottom-right)
diagonals2 = defaultdict(int)   # key: row + column (top-right to bottom-left)

A set named lamps stores each active lamp as a tuple (row, column). Because a set eliminates duplicates, the initialization loop increments each counter exactly once per distinct lamp.

Initialization of lamp counters

The first logical block transforms the raw lamp list into a set of unique positions and populates the four dictionaries:

lamps = set((y, x) for y, x in lamps)
for y, x in lamps:
    horizontal[y]     += 1
    vertical[x]       += 1
    diagonals1[y - x] += 1
    diagonals2[y + x] += 1

By using the arithmetic expressions y - x and y + x as keys, the code captures the two diagonal families without needing explicit coordinate traversal.

Query processing

For each query the algorithm computes the total illumination contribution from the four line families:

result = horizontal[y] + vertical[x] + diagonals1[y - x] + diagonals2[y + x]
yield 1 if result > 0 else 0

If any of the counters is non-zero, the cell is illuminated and the generator yields 1; otherwise it yields 0. The use of a generator (yield) allows the caller to consume results lazily, which can be advantageous when the result list is large.

Deactivating surrounding lamps

After answering a query, the algorithm iterates over the 3 × 3 region centered at the query coordinates, removing any lamp found there and decrementing the associated line counters:

for yy in range(y - 1, y + 1 + 1):
    for xx in range(x - 1, x + 1 + 1):
        if (yy, xx) in lamps:
            lamps.discard((yy, xx))
            if horizontal[yy] > 0:
                horizontal[yy] -= 1
            if vertical[xx] > 0:
                vertical[xx] -= 1
            if diagonals1[yy - xx] > 0:
                diagonals1[yy - xx] -= 1
            if diagonals2[yy + xx] > 0:
                diagonals2[yy + xx] -= 1

The nested loops cover exactly nine positions: the query cell itself and its eight immediate neighbors. The discard method removes the lamp without raising an exception if the element is absent, which simplifies the control flow. The conditional decrements guard against negative counts, ensuring that the dictionaries reflect the true number of active lamps on each line.

Edge-case handling

The code gracefully handles several boundary conditions:

• Duplicate lamp entries - By converting the lamp list to a set, repeated coordinates are collapsed, preventing double counting in the line dictionaries.
• Queries on the grid border - The range loops for deactivation use y - 1 to y + 1 inclusive. When y or x is at the edge (0 or n - 1), the generated coordinates may fall outside the grid. The membership test (yy, xx) in lamps automatically filters out-of-bounds positions because such coordinates are never present in the lamp set.
• Empty illumination - If no lamp influences a query cell, all four counters return zero, and the generator yields 0. The subsequent deactivation loop still executes, but the membership test quickly fails, leaving the state unchanged.
• Repeated queries on the same cell - After the first query, any lamp in the surrounding 3 × 3 block has been removed, so subsequent queries on that cell will see zero illumination unless other lamps elsewhere affect the same row, column, or diagonal. The counters have already been decremented, so the result reflects the updated state.

Performance optimizations

Several design choices contribute to efficient execution:

• Hash-based counting - Using dictionaries keyed by line identifiers provides O(1) access for increment, decrement, and lookup operations, eliminating the need for scanning rows, columns, or diagonals.
• Set for lamp storage - The lamps set enables constant-time existence checks and removal. This is crucial for the deactivation step, where up to nine look-ups occur per query.
• Lazy result generation - The function is written as a generator (yield). This avoids constructing an intermediate list of results, reducing memory pressure when the caller processes results incrementally.
• Conditional decrements - Before reducing a counter, the code checks that the current value is positive. This prevents unnecessary dictionary writes when the counter is already zero, which can be beneficial in tight loops.
• Compact arithmetic for diagonals - Representing each diagonal by a simple arithmetic expression (row - column or row + column) avoids storing explicit collections of coordinates for each diagonal, saving both time and space.

Overall, the implementation leverages hash-based data structures and careful state management to achieve fast query responses and minimal overhead during lamp deactivation.

Imagine a giant board full of light bulbs. Some bulbs are turned on, and you want to know if a specific spot on the board is bright.

To figure this out, this code keeps track of four special lists. It remembers how many lights are in each row, each column, and on both types of diagonal lines that go across the board. Every time a light is turned on, the code adds one to the count for that lamp's row, column, and diagonals.

When a query asks about a spot on the board, the code checks those four lists. If any of those lists show that there is at least one light shining on that spot, the answer is that the spot is lit up.

Once a spot is checked, the code looks around that spot and the eight neighboring spots to see if any lamps are there. If it finds any lamps, it turns them off. Turning off a lamp means going back to those four lists and subtracting one from the counts for that lamp's row, column, and diagonals. This keeps the information about which lamps are shining perfectly up to date as the lights start to go out.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++			Python	Java		TS
	WalkCCC	C++			Python	Java
	leetcode.ca	C++			Python	Java	Go	TS
	LeetcodeHelp	C++			Python	Java
	Progiez	C++			Python	Java
github	BigEggStudy			C#
	black-shadows	C++
	charles-wangkai					Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007				Python
	suxrobGM			C#
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality