1001. Grid Illumination

Description

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.

 

Example 1:

Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]
Explanation: We have the initial grid with all lamps turned off. In the above picture we see the grid after turning on the lamp at grid[0][0] then turning on the lamp at grid[4][4].
The 0th query asks if the lamp at grid[1][1] is illuminated or not (the blue square). It is illuminated, so set ans[0] = 1. Then, we turn off all lamps in the red square.

The 1st query asks if the lamp at grid[1][0] is illuminated or not (the blue square). It is not illuminated, so set ans[1] = 0. Then, we turn off all lamps in the red rectangle.

Example 2:

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

Example 3:

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

 

Constraints:

• 1 <= n <= 109
• 0 <= lamps.length <= 20000
• 0 <= queries.length <= 20000
• lamps[i].length == 2
• 0 <= rowi, coli < n
• queries[j].length == 2
• 0 <= rowj, colj < n

 

Solutions

Solution: Hash Map

• Time complexity: O(lamps.length + queries.length)
• Space complexity: O(lamps.length)

 

JavaScript

/**
 * @param {number} n
 * @param {number[][]} lamps
 * @param {number[][]} queries
 * @return {number[]}
 */
const gridIllumination = function (n, lamps, queries) {
  const lampsSet = new Set();
  const rowMemo = new Map();
  const colMemo = new Map();
  const diagonalMemo = new Map();
  const negativeDiagonalMemo = new Map();
  const adjacent = [
    [-1, -1],
    [-1, 0],
    [-1, 1],
    [0, -1],
    [0, 0],
    [0, 1],
    [1, -1],
    [1, 0],
    [1, 1],
  ];

  for (const [row, col] of lamps) {
    const key = `${row},${col}`;

    if (lampsSet.has(key)) continue;
    lampsSet.add(key);
    rowMemo.set(row, (rowMemo.get(row) ?? 0) + 1);
    colMemo.set(col, (colMemo.get(col) ?? 0) + 1);
    diagonalMemo.set(row + col, (diagonalMemo.get(row + col) ?? 0) + 1);
    negativeDiagonalMemo.set(row - col, (negativeDiagonalMemo.get(row - col) ?? 0) + 1);
  }

  return queries.map(([row, col]) => {
    const isIllumination =
      rowMemo.get(row) || colMemo.get(col) || diagonalMemo.get(row + col) || negativeDiagonalMemo.get(row - col);

    for (const offset of adjacent) {
      const offsetRow = row + offset[0];
      const offsetCol = col + offset[1];
      const key = `${offsetRow},${offsetCol}`;

      if (offsetRow < 0 || offsetRow >= n || offsetCol < 0 || offsetCol >= n) continue;
      if (!lampsSet.has(key)) continue;
      const rowCount = rowMemo.get(offsetRow) - 1;
      const colCount = colMemo.get(offsetCol) - 1;
      const diagonalCount = diagonalMemo.get(offsetRow + offsetCol) - 1;
      const negativeDiagonalCount = negativeDiagonalMemo.get(offsetRow - offsetCol) - 1;

      rowCount ? rowMemo.set(offsetRow, rowCount) : rowMemo.delete(offsetRow);
      colCount ? colMemo.set(offsetCol, colCount) : colMemo.delete(offsetCol);

      diagonalCount
        ? diagonalMemo.set(offsetRow + offsetCol, diagonalCount)
        : diagonalMemo.delete(offsetRow + offsetCol);

      negativeDiagonalCount
        ? negativeDiagonalMemo.set(offsetRow - offsetCol, negativeDiagonalCount)
        : negativeDiagonalMemo.delete(offsetRow - offsetCol);

      lampsSet.delete(key);
    }

    return isIllumination ? 1 : 0;
  });
};