Grid Illumination — Hard Problem & Solution

Problem statement

On an n × n grid, each cell in lamps holds a lamp that is switched on (duplicates in lamps are the same single lamp). A lit lamp illuminates its whole row, its whole column and both of its diagonals.

Answer the queries in order. For each queries[i] = [row, col], record 1 if that cell is illuminated and 0 otherwise, and then switch off every lamp in the 3 × 3 block centred on it (the cell itself and its eight neighbours), ignoring any part of the block outside the grid.

Example 1

Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]
Explanation: The first query is on the lamp's diagonal; answering it also switches that lamp off.

Example 2

Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]
Output: [1,1]
Explanation: The second query is lit by the lamp at `(4,4)`, which the first query did not reach.

Example 3

Input: n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]]
Output: [1,1,0]

Constraints

• 1 <= n <= 10^4
• 0 <= lamps.length <= 20000
• 0 <= queries.length <= 20000
• lamps[i].length == 2
• 0 <= lamps[i][0], lamps[i][1] < n
• queries[j].length == 2
• 0 <= queries[j][0], queries[j][1] < n

How to solve Grid Illumination

Track, for each of the four line families, how many lit lamps lie on each line. A query is lit if any of its four lines has a non-zero count, and switching a lamp off decrements the four counts it contributed to.

Approach

1. Insert each distinct lamp into a set and increment its row, column, r - c and r + c counters.
2. For a query, read those four counters; a positive one means the cell is lit.
3. Then, for each of the nine cells in the block, if a lamp is still on there, remove it and decrement its four counters.

Why it works

The row, column, and two diagonals through a cell are exactly the lines a lamp must lie on to illuminate it, so four counters are a complete test. Keeping a set of lamps still on is what makes turning off idempotent — switching off an already-dark cell must not decrement anything, and the same duplicate lamp must be inserted only once.

Complexity

• Time — O(lamps + queries)
• Space — O(lamps)

Pitfalls

• Duplicate entries in lamps describe one lamp and must be counted once.
• The lamp's own cell is part of the 3 × 3 block that the query switches off.
• Decrementing a counter for a lamp that was already off corrupts every later query.

Reference solution

Python

from typing import List
from collections import defaultdict

def gridIllumination(n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
    rows, cols = defaultdict(int), defaultdict(int)
    diag, anti = defaultdict(int), defaultdict(int)
    on = set()
    for r, c in lamps:
        if (r, c) in on:
            continue
        on.add((r, c))
        rows[r] += 1
        cols[c] += 1
        diag[r - c] += 1
        anti[r + c] += 1
    out = []
    for r, c in queries:
        lit = rows[r] > 0 or cols[c] > 0 or diag[r - c] > 0 or anti[r + c] > 0
        out.append(1 if lit else 0)
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and (nr, nc) in on:
                    on.discard((nr, nc))
                    rows[nr] -= 1
                    cols[nc] -= 1
                    diag[nr - nc] -= 1
                    anti[nr + nc] -= 1
    return out

JavaScript

var gridIllumination = function(n, lamps, queries) {
    var rows = new Map(), cols = new Map(), diag = new Map(), anti = new Map();
    var on = new Set();
    var bump = function(m, k, d) {
        var cur = m.get(k);
        var v = (cur === undefined ? 0 : cur) + d;
        if (v === 0) m["delete"](k); else m.set(k, v);
    };
    var get = function(m, k) {
        var cur = m.get(k);
        return cur === undefined ? 0 : cur;
    };
    var i, r, c, key;
    for (i = 0; i < lamps.length; i++) {
        r = lamps[i][0];
        c = lamps[i][1];
        key = r * n + c;
        if (on.has(key)) continue;
        on.add(key);
        bump(rows, r, 1);
        bump(cols, c, 1);
        bump(diag, r - c, 1);
        bump(anti, r + c, 1);
    }
    var out = [];
    for (i = 0; i < queries.length; i++) {
        r = queries[i][0];
        c = queries[i][1];
        var lit = get(rows, r) > 0 || get(cols, c) > 0 || get(diag, r - c) > 0 || get(anti, r + c) > 0;
        out.push(lit ? 1 : 0);
        for (var dr = -1; dr <= 1; dr++) {
            for (var dc = -1; dc <= 1; dc++) {
                var nr = r + dr, nc = c + dc;
                if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
                key = nr * n + nc;
                if (!on.has(key)) continue;
                on["delete"](key);
                bump(rows, nr, -1);
                bump(cols, nc, -1);
                bump(diag, nr - nc, -1);
                bump(anti, nr + nc, -1);
            }
        }
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Count Ways to Make Array With Product Hard
• The Number of Good Subsets Hard
• Number of Ways to Reorder Array to Get Same BST Hard
• Make Array Strictly Increasing Hard
• Odd Even Jump Hard
• Maximum Number of Events That Can Be Attended II Hard