Grid Illumination

hard hash map grid diagonals

Problem

On an n × n grid of lamps, you are given the positions of lamps that are turned on. A lit lamp illuminates its entire row, column, and both diagonals. For each query [r, c], report 1 if cell (r, c) is illuminated, else 0. After answering, turn off the lamp at (r, c) and the 8 lamps adjacent to it (if any). Return the answers for all queries.

Inputn = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]

Output[1, 0]

(1,1) shares a diagonal with lamp (0,0) → lit (1). Answering the first query turns off lamp (0,0) and its neighbors, so (1,0) is no longer lit → 0.

lamps (e.g. 0,0; 4,4)

queries (e.g. 1,1; 1,0)

def grid_illumination(n, lamps, queries):
    from collections import defaultdict
    rows, cols, diag, anti = (defaultdict(int) for _ in range(4))
    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
    ans = []
    for r, c in queries:
        lit = rows[r] or cols[c] or diag[r - c] or anti[r + c]
        ans.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 (nr, nc) in on:
                    on.remove((nr, nc))
                    rows[nr] -= 1; cols[nc] -= 1
                    diag[nr - nc] -= 1; anti[nr + nc] -= 1
    return ans

function gridIllumination(n, lamps, queries) {
  const rows = new Map(), cols = new Map(), diag = new Map(), anti = new Map();
  const on = new Set();
  const bump = (m, k, d) => m.set(k, (m.get(k) || 0) + d);
  for (const [r, c] of lamps) {
    const key = r + "," + 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);
  }
  const ans = [];
  for (const [r, c] of queries) {
    const lit = (rows.get(r) || cols.get(c) || diag.get(r - c) || anti.get(r + c)) ? 1 : 0;
    ans.push(lit);
    for (let dr = -1; dr <= 1; dr++) {
      for (let dc = -1; dc <= 1; dc++) {
        const nr = r + dr, nc = c + dc, key = nr + "," + nc;
        if (on.has(key)) {
          on.delete(key);
          bump(rows, nr, -1); bump(cols, nc, -1);
          bump(diag, nr - nc, -1); bump(anti, nr + nc, -1);
        }
      }
    }
  }
  return ans;
}

class Solution {
    public 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<Long> on = new HashSet<>();
        for (int[] l : lamps) {
            long key = (long) l[0] * n + l[1];
            if (!on.add(key)) continue;
            rows.merge(l[0], 1, Integer::sum); cols.merge(l[1], 1, Integer::sum);
            diag.merge(l[0] - l[1], 1, Integer::sum); anti.merge(l[0] + l[1], 1, Integer::sum);
        }
        int[] ans = 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;
            ans[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;
                    long key = (long) nr * n + nc;
                    if (on.remove(key)) {
                        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 ans;
    }
}

vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
    unordered_map<int,int> rows, cols, diag, anti;
    unordered_set<long long> on;
    for (auto& l : lamps) {
        long long key = (long long) l[0] * n + l[1];
        if (!on.insert(key).second) continue;
        rows[l[0]]++; cols[l[1]]++; diag[l[0] - l[1]]++; anti[l[0] + l[1]]++;
    }
    vector<int> ans;
    for (auto& q : queries) {
        int r = q[0], c = q[1];
        bool lit = rows[r] || cols[c] || diag[r - c] || anti[r + c];
        ans.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;
                long long key = (long long) nr * n + nc;
                if (on.erase(key)) {
                    rows[nr]--; cols[nc]--; diag[nr - nc]--; anti[nr + nc]--;
                }
            }
    }
    return ans;
}

Explanation

The grid can be enormous, so we never build it. Instead we notice a cell is lit when some lamp shares its row, its column, or one of its two diagonals. We just need to count, for each of those four lines, how many lamps sit on it.

We keep four hash maps: rows keyed by r, cols keyed by c, diag keyed by r - c (the same on a "\\" diagonal), and anti keyed by r + c (the same on a "/" diagonal). A separate on set remembers which lamps are actually live so duplicates are not double-counted.

A query (r, c) is lit if any of rows[r], cols[c], diag[r-c], or anti[r+c] is positive — an O(1) check. After answering we switch off the lamp at (r, c) and its 8 neighbors, decrementing the four maps for each one we remove.

Example: lamps = [[0,0],[4,4]]. Lamp (0,0) sits on diagonal r-c = 0; query (1,1) also has r-c = 0, so diag[0] > 0 means it is lit, giving 1.

Because each query and each turn-off touches only a constant number of map entries, the whole thing runs in time proportional to the number of lamps plus queries.

Time: O(L + Q) Space: O(L)