LeetCode 1001: Grid Illumination Solution

Master LeetCode problem 1001 (Grid Illumination), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1001. Grid Illumination

Hard

Array Hash Table

Problem Explanation

Explanation

To solve this problem, we can maintain four hash maps: one for rows, one for columns, and two for diagonals. When we turn on a lamp, we increment the corresponding counter in each hash map. When checking if a cell is illuminated, we check if the row, column, or diagonal of that cell has any lamp that can illuminate it. We also need to handle turning off the lamps and updating the hash maps accordingly.

Algorithm:

Initialize hash maps for rows, columns, and two diagonals.
Iterate through the lamps array and turn on lamps, updating the hash maps.
Iterate through the queries array and check if the cell is illuminated based on hash maps.
Turn off the lamp at the queried cell and its adjacent lamps, updating hash maps.
Return the result array.

Time Complexity: O(n + lamps.length + queries.length) where n is the size of the grid.

Space Complexity: O(n + lamps.length)

Solution Code

class Solution {
    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        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<String> lampSet = new HashSet<>();

        for (int[] lamp : lamps) {
            int r = lamp[0];
            int c = lamp[1];
            rows.put(r, rows.getOrDefault(r, 0) + 1);
            cols.put(c, cols.getOrDefault(c, 0) + 1);
            diag1.put(r - c, diag1.getOrDefault(r - c, 0) + 1);
            diag2.put(r + c, diag2.getOrDefault(r + c, 0) + 1);
            lampSet.add(r + "," + c);
        }

        int[] result = new int[queries.length];
        int[] dr = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
        int[] dc = {-1, 0, 1, -1, 0, 1, -1, 0, 1};

        for (int i = 0; i < queries.length; i++) {
            int r = queries[i][0];
            int c = queries[i][1];

            if (rows.getOrDefault(r, 0) > 0 || cols.getOrDefault(c, 0) > 0 ||
                    diag1.getOrDefault(r - c, 0) > 0 || diag2.getOrDefault(r + c, 0) > 0) {
                result[i] = 1;
            }

            for (int j = 0; j < 9; j++) {
                int nr = r + dr[j];
                int nc = c + dc[j];
                if (lampSet.contains(nr + "," + nc)) {
                    rows.put(nr, rows.getOrDefault(nr, 1) - 1);
                    cols.put(nc, cols.getOrDefault(nc, 1) - 1);
                    diag1.put(nr - nc, diag1.getOrDefault(nr - nc, 1) - 1);
                    diag2.put(nr + nc, diag2.getOrDefault(nr + nc, 1) - 1);
                    lampSet.remove(nr + "," + nc);
                }
            }
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1001 (Grid Illumination)?

This page provides optimized solutions for LeetCode problem 1001 (Grid Illumination) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1001 (Grid Illumination)?

The time complexity for LeetCode 1001 (Grid Illumination) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1001 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1001 in Java, C++, or Python.

Back to LeetCode Solutions