Grid illumination

Array Hash Table

39.0% acceptance

Feb 25, 2026

648

161

There is a 2D grid of size n x n where each cell of this grid has a lamp that is initially turned off. You are given a 2D array of lamp positions lamps, where lamps[i] = [rowi, coli] indicates that the lamp at grid[rowi][coli] is turned on. Even if the same lamp is listed more than once, it is turned on. When a lamp is turned on, it illuminates its cell and all other cells in the same row, column, or diagonal. You are also given another 2D array queries, where queries[j] = [rowj, colj]. For the jth query, determine whether grid[rowj][colj] is illuminated or not. After answering the jth query, turn off the lamp at grid[rowj][colj] and its 8 adjacent lamps if they exist. A lamp is adjacent if its cell shares either a side or corner with grid[rowj][colj]. Return an array of integers ans, where ans[j] should be 1 if the cell in the jth query was illuminated, or 0 if the lamp was not.

Solution

Rust

Time O(n³)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;
use std::collections::HashSet;

impl Solution {
  pub fn grid_illumination(n: i32, lamps: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
    let mut row: HashMap<i32,i32> = HashMap::new();
    let mut col: HashMap<i32,i32> = HashMap::new();
    let mut diag: HashMap<i32,i32> = HashMap::new();
    let mut anti: HashMap<i32,i32> = HashMap::new();
    let mut on: HashSet<(i32,i32)> = HashSet::new();
    for l in &lamps {
      let (r,c) = (l[0],l[1]);
      if on.insert((r,c)) {
        *row.entry(r).or_insert(0) += 1;
        *col.entry(c).or_insert(0) += 1;
        *diag.entry(r-c).or_insert(0) += 1;
        *anti.entry(r+c).or_insert(0) += 1;
      }
    }
    let mut ans = Vec::new();
    for q in &queries {
      let (r,c) = (q[0],q[1]);
      let lit = *row.get(&r).unwrap_or(&0) > 0 || *col.get(&c).unwrap_or(&0) > 0
        || *diag.get(&(r-c)).unwrap_or(&0) > 0 || *anti.get(&(r+c)).unwrap_or(&0) > 0;
      ans.push(if lit { 1 } else { 0 });
      for dr in -1..=1i32 { for dc in -1..=1i32 {
        let (nr,nc) = (r+dr, c+dc);
        if nr >= 0 && nr < n && nc >= 0 && nc < n && on.remove(&(nr,nc)) {
          *row.entry(nr).or_insert(0) -= 1;
          *col.entry(nc).or_insert(0) -= 1;
          *diag.entry(nr-nc).or_insert(0) -= 1;
          *anti.entry(nr+nc).or_insert(0) -= 1;
        }
      }}
    }
    ans
  }
}