Skip to content

1001. Grid Illumination

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
 public:
  vector<int> gridIllumination(int n, vector<vector<int>>& lamps,
                               vector<vector<int>>& queries) {
    vector<int> ans;
    unordered_map<int, int> rows;
    unordered_map<int, int> cols;
    unordered_map<int, int> diag1;
    unordered_map<int, int> diag2;
    unordered_set<pair<int, int>, PairHash> lampsSet;

    for (const vector<int>& lamp : lamps) {
      const int i = lamp[0];
      const int j = lamp[1];
      if (lampsSet.insert({i, j}).second) {
        ++rows[i];
        ++cols[j];
        ++diag1[i + j];
        ++diag2[i - j];
      }
    }

    for (const vector<int>& query : queries) {
      const int i = query[0];
      const int j = query[1];
      if (rows[i] || cols[j] || diag1[i + j] || diag2[i - j]) {
        ans.push_back(1);
        for (int y = max(0, i - 1); y < min(n, i + 2); ++y)
          for (int x = max(0, j - 1); x < min(n, j + 2); ++x)
            if (lampsSet.erase({y, x})) {
              --rows[y];
              --cols[x];
              --diag1[y + x];
              --diag2[y - x];
            }
      } else {
        ans.push_back(0);
      }
    }

    return ans;
  }

 private:
  struct PairHash {
    size_t operator()(const pair<int, int>& p) const {
      return p.first ^ p.second;
    }
  };
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
  public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
    List<Integer> ans = new ArrayList<>();
    Map<Integer, Integer> rows = new HashMap<>();
    Map<Integer, Integer> cols = new HashMap<>();
    Map<Integer, Integer> diag1 = new HashMap<>();
    Map<Integer, Integer> diag2 = new HashMap<>();
    Set<Long> lampsSet = new HashSet<>();

    for (int[] lamp : lamps) {
      final int i = lamp[0];
      final int j = lamp[1];
      if (lampsSet.add(hash(i, j))) {
        rows.merge(i, 1, Integer::sum);
        cols.merge(j, 1, Integer::sum);
        diag1.merge(i + j, 1, Integer::sum);
        diag2.merge(i - j, 1, Integer::sum);
      }
    }

    for (int[] query : queries) {
      final int i = query[0];
      final int j = query[1];
      if (rows.getOrDefault(i, 0) > 0 || cols.getOrDefault(j, 0) > 0 ||
          diag1.getOrDefault(i + j, 0) > 0 || diag2.getOrDefault(i - j, 0) > 0) {
        ans.add(1);
        for (int y = Math.max(0, i - 1); y < Math.min(n, i + 2); ++y)
          for (int x = Math.max(0, j - 1); x < Math.min(n, j + 2); ++x)
            if (lampsSet.remove(hash(y, x))) {
              rows.merge(y, 1, Integer::sum);
              cols.merge(x, 1, Integer::sum);
              diag1.merge(y + x, 1, Integer::sum);
              diag2.merge(y - x, 1, Integer::sum);
            }
      } else {
        ans.add(0);
      }
    }

    return ans.stream().mapToInt(Integer::intValue).toArray();
  }

  private long hash(int i, int j) {
    return ((long) i << 32) + j;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
  def gridIllumination(
      self,
      n: int,
      lamps: list[list[int]],
      queries: list[list[int]],
  ) -> list[int]:
    ans = []
    rows = collections.Counter()
    cols = collections.Counter()
    diag1 = collections.Counter()
    diag2 = collections.Counter()
    lampsSet = set()

    for i, j in lamps:
      if (i, j) not in lampsSet:
        lampsSet.add((i, j))
        rows[i] += 1
        cols[j] += 1
        diag1[i + j] += 1
        diag2[i - j] += 1

    for i, j in queries:
      if rows[i] or cols[j] or diag1[i + j] or diag2[i - j]:
        ans.append(1)
        for y in range(max(0, i - 1), min(n, i + 2)):
          for x in range(max(0, j - 1), min(n, j + 2)):
            if (y, x) in lampsSet:
              lampsSet.remove((y, x))
              rows[y] -= 1
              cols[x] -= 1
              diag1[y + x] -= 1
              diag2[y - x] -= 1
      else:
        ans.append(0)

    return ans