In this guide, you will get 1001. Grid Illumination LeetCode Solution with the best time and space complexity. The solution to Grid Illumination problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
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;
}
};
}; /* code provided by PROGIEZ */
1001. Grid Illumination LeetCode Solution in Java
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;
}
} // code provided by PROGIEZ
1001. Grid Illumination LeetCode Solution in Python
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 # code by PROGIEZ
