Grid Illumination

Hard
926.

Grid Illumination

Grid Illumination is a hard coding problem on arrays, hash table and matrix, asked in Amazon, Google, Adobe and Dropbox interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} lamps
 * @param {number[][]} queries
 * @return {number[]}
 */
var gridIllumination = function(n, lamps, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Grid Illumination — Solution in Python, Java & C++

Grid Illumination solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on arrays and hash table.

Grid Illumination is a hard coding problem on arrays, hash table and matrix, asked in Amazon, Google, Adobe and Dropbox interviews.

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

Hints for Grid Illumination

  1. Hint 1

    Never build the grid: n can be 10 000, and only the lamps matter.

  2. Hint 2

    A cell is illuminated exactly when some lamp shares its row, its column, or one of its two diagonals.

  3. Hint 3

    Keep four counters — by row, by column, by row - col and by row + col — plus a set of the lamps that are still on.

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

Java

public static int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
    Map<Integer, Integer> rows = new HashMap<>(), cols = new HashMap<>();
    Map<Integer, Integer> diag = new HashMap<>(), anti = new HashMap<>();
    Set<Integer> on = new HashSet<>();
    for (int[] lamp : lamps) {
        int r = lamp[0], c = lamp[1];
        if (!on.add(r * n + c)) continue;
        rows.merge(r, 1, Integer::sum);
        cols.merge(c, 1, Integer::sum);
        diag.merge(r - c, 1, Integer::sum);
        anti.merge(r + c, 1, Integer::sum);
    }
    int[] out = new int[queries.length];
    for (int q = 0; q < queries.length; q++) {
        int r = queries[q][0], c = queries[q][1];
        boolean lit = rows.getOrDefault(r, 0) > 0 || cols.getOrDefault(c, 0) > 0
                || diag.getOrDefault(r - c, 0) > 0 || anti.getOrDefault(r + c, 0) > 0;
        out[q] = lit ? 1 : 0;
        for (int dr = -1; dr <= 1; dr++) {
            for (int dc = -1; dc <= 1; dc++) {
                int nr = r + dr, nc = c + dc;
                if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
                if (!on.remove(nr * n + nc)) continue;
                rows.merge(nr, -1, Integer::sum);
                cols.merge(nc, -1, Integer::sum);
                diag.merge(nr - nc, -1, Integer::sum);
                anti.merge(nr + nc, -1, Integer::sum);
            }
        }
    }
    return out;
}

C++

vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
    unordered_map<int, int> rows, cols, diag, anti;
    unordered_set<int> on;
    for (auto& lamp : lamps) {
        int r = lamp[0], c = lamp[1];
        if (!on.insert(r * n + c).second) continue;
        rows[r]++;
        cols[c]++;
        diag[r - c]++;
        anti[r + c]++;
    }
    vector<int> out;
    for (auto& q : queries) {
        int r = q[0], c = q[1];
        bool lit = rows[r] > 0 || cols[c] > 0 || diag[r - c] > 0 || anti[r + c] > 0;
        out.push_back(lit ? 1 : 0);
        for (int dr = -1; dr <= 1; dr++) {
            for (int dc = -1; dc <= 1; dc++) {
                int nr = r + dr, nc = c + dc;
                if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
                if (on.erase(nr * n + nc) == 0) continue;
                rows[nr]--;
                cols[nc]--;
                diag[nr - nc]--;
                anti[nr + nc]--;
            }
        }
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets