What is the time complexity of Grid Illumination?

The optimal solution has a time complexity of O(L + Q).

What data structures are used to solve Grid Illumination?

This problem uses Array, Hash Table. Understanding these concepts is essential for solving this Hard problem efficiently.

What are the key insights for solving Grid Illumination?

Insight 1: Using direct grid representation is not feasible due to potentially huge grid size (up to 10^9). Therefore, storing the state of each cell individually is space inefficient. Hash tables are suitable for storing the states of lit lamps, rows, columns, and diagonals. Insight 2: Instead of representing the entire grid, we only need to keep track of the lit lamps and the counts of illuminated rows, columns, and diagonals using hash tables (or counters).

Which companies ask LeetCode 1001. Grid Illumination in interviews?

This problem is frequently asked at Dropbox.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Grid Illumination - LeetCode 1001 Solution

Grid Illumination - Complete Solution Guide

Grid Illumination is LeetCode problem 1001, a Hard level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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] = [row i , col i ] indicates that the lamp at grid[row i ][col i ] 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] = [row j ,

Detailed Explanation

The problem asks you to simulate a grid of lamps that can illuminate rows, columns, and diagonals. You're given an initial set of lit lamps and a series of queries. Each query asks if a particular cell is illuminated. If it is, you record '1', otherwise '0'. After answering each query, you turn off the lamp at the queried cell and its 8 adjacent neighbors (if they exist). The goal is to return an array representing the answers to each query.

Solution Approach

The solution uses a combination of hash tables (or counters) and a set to efficiently track the state of illuminated rows, columns, diagonals, and the lit lamps themselves. The algorithm iterates through the queries. For each query, it checks if the cell is illuminated based on the counts in the hash tables. Then, it turns off the lamp at the query cell and its 8 neighbors by decrementing the counts in the hash tables and removing the corresponding lamp positions from the set.

Step-by-Step Algorithm

Step 1: Initialize a set `lamp_positions` to store the coordinates of all lit lamps, to avoid duplicates, and four hash tables (`row_counts`, `col_counts`, `diag1_counts`, `diag2_counts`) to store the counts of illuminated rows, columns, and diagonals, respectively.
Step 2: Iterate through the `lamps` array. For each lamp, if its position isn't already in `lamp_positions`, add it to the set and increment the corresponding counts in `row_counts`, `col_counts`, `diag1_counts`, and `diag2_counts`. `diag1_counts` tracks r - c, representing one diagonal family, while `diag2_counts` tracks r + c, representing the other diagonal family.
Step 3: Initialize an empty list `ans` to store the results of each query.
Step 4: Iterate through the `queries` array. For each query, check if the cell `(qr, qc)` is illuminated by checking if `row_counts[qr] > 0`, `col_counts[qc] > 0`, `diag1_counts[qr - qc] > 0`, or `diag2_counts[qr + qc] > 0`. Append 1 to `ans` if illuminated, and 0 otherwise.
Step 5: Turn off the lamp at `(qr, qc)` and its 8 adjacent neighbors. Iterate through a 3x3 grid centered at `(qr, qc)`. For each neighbor `(nr, nc)`, check if the lamp is lit (exists in `lamp_positions`). If it is, remove it from `lamp_positions` and decrement the corresponding counts in `row_counts`, `col_counts`, `diag1_counts`, and `diag2_counts`.
Step 6: After processing all queries, return the `ans` list.

Key Insights

Insight 1: Using direct grid representation is not feasible due to potentially huge grid size (up to 10^9). Therefore, storing the state of each cell individually is space inefficient. Hash tables are suitable for storing the states of lit lamps, rows, columns, and diagonals.
Insight 2: Instead of representing the entire grid, we only need to keep track of the lit lamps and the counts of illuminated rows, columns, and diagonals using hash tables (or counters).
Insight 3: Efficiently managing the lamps to be turned off after each query is crucial. A set can be used to quickly check and remove lamps that need to be turned off during the query process.

Complexity Analysis

Time Complexity: O(L + Q)

Space Complexity: O(L)

Topics

This problem involves: Array, Hash Table.

Companies

Asked at: Dropbox.

Grid Illumination | LeetCode 1001

Hard

Array Hash Table

Time: O(L + Q)Space: O(L)

Solution Code

Available in:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

class Solution {
    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        Set<String> lamp_positions = new HashSet<>();
        Map<Integer, Integer> row_counts = new HashMap<>();
        Map<Integer, Integer> col_counts = new HashMap<>();
        Map<Integer, Integer> diag1_counts = new HashMap<>();
        Map<Integer, Integer> diag2_counts = new HashMap<>();

        for (int[] lamp : lamps) {
            int r = lamp[0];
            int c = lamp[1];
            String pos = r + "," + c;
            if (!lamp_positions.contains(pos)) {
                lamp_positions.add(pos);
                row_counts.put(r, row_counts.getOrDefault(r, 0) + 1);
                col_counts.put(c, col_counts.getOrDefault(c, 0) + 1);
                diag1_counts.put(r - c, diag1_counts.getOrDefault(r - c, 0) + 1);
                diag2_counts.put(r + c, diag2_counts.getOrDefault(r + c, 0) + 1);
            }
        }

        List<Integer> ans = new ArrayList<>();

        for (int[] query : queries) {
            int qr = query[0];
            int qc = query[1];

            if ((row_counts.containsKey(qr) && row_counts.get(qr) > 0) ||
                (col_counts.containsKey(qc) && col_counts.get(qc) > 0) ||
                (diag1_counts.containsKey(qr - qc) && diag1_counts.get(qr - qc) > 0) ||
                (diag2_counts.containsKey(qr + qc) && diag2_counts.get(qr + qc) > 0)) {
                ans.add(1);
            } else {
                ans.add(0);
            }

            for (int dr = -1; dr <= 1; dr++) {
                for (int dc = -1; dc <= 1; dc++) {
                    int nr = qr + dr;
                    int nc = qc + dc;
                    String npos = nr + "," + nc;

                    if (lamp_positions.contains(npos)) {
                        lamp_positions.remove(npos);

                        row_counts.put(nr, row_counts.get(nr) - 1);
                        if(row_counts.get(nr) == 0){
                            row_counts.remove(nr);
                        }
                        
                        col_counts.put(nc, col_counts.get(nc) - 1);
                         if(col_counts.get(nc) == 0){
                            col_counts.remove(nc);
                        }

                        diag1_counts.put(nr - nc, diag1_counts.get(nr - nc) - 1);
                         if(diag1_counts.get(nr - nc) == 0){
                            diag1_counts.remove(nr - nc);
                        }

                        diag2_counts.put(nr + nc, diag2_counts.get(nr + nc) - 1);
                         if(diag2_counts.get(nr + nc) == 0){
                            diag2_counts.remove(nr + nc);
                        }
                    }
                }
            }
        }
        
        int[] result = new int[ans.size()];
        for(int i = 0; i < ans.size(); i++){
            result[i] = ans.get(i);
        }

        return result;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1001: Grid Illumination - Detailed explanation and solution approaches.

Topics

Array Hash Table

Companies

Dropbox

Stats

Difficulty:Hard

Languages:4

Companies:1

Problem #:1001

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Initialize a set `lamp_positions` to store the coordinates of all lit lamps, to avoid duplicates, and four hash tables (`row_counts`, `col_counts`, `diag1_counts`, `diag2_counts`) to store the counts of illuminated rows, columns, and diagonals, respectively.
2
Step 2: Iterate through the `lamps` array. For each lamp, if its position isn't already in `lamp_positions`, add it to the set and increment the corresponding counts in `row_counts`, `col_counts`, `diag1_counts`, and `diag2_counts`. `diag1_counts` tracks r - c, representing one diagonal family, while `diag2_counts` tracks r + c, representing the other diagonal family.
3
Step 3: Initialize an empty list `ans` to store the results of each query.
4
Step 4: Iterate through the `queries` array. For each query, check if the cell `(qr, qc)` is illuminated by checking if `row_counts[qr] > 0`, `col_counts[qc] > 0`, `diag1_counts[qr - qc] > 0`, or `diag2_counts[qr + qc] > 0`. Append 1 to `ans` if illuminated, and 0 otherwise.
5
Step 5: Turn off the lamp at `(qr, qc)` and its 8 adjacent neighbors. Iterate through a 3x3 grid centered at `(qr, qc)`. For each neighbor `(nr, nc)`, check if the lamp is lit (exists in `lamp_positions`). If it is, remove it from `lamp_positions` and decrement the corresponding counts in `row_counts`, `col_counts`, `diag1_counts`, and `diag2_counts`.
6
Step 6: After processing all queries, return the `ans` list.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(L + Q)

💾

Space Complexity

O(L)

📝

Why?

The time complexity is O(L + Q) because initializing the counters takes O(L) time and processing each query involves checking for illumination (O(1)) and turning off at most 9 lamps (O(1) each), so it is O(Q). The space complexity is O(L) because we are storing the lamp positions and counts corresponding to the number of lamps.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using a defaultdict in Python

Instead of using collections.Counter in python, defaultdict(int) can be used. It automatically assigns 0 as the default value to any key that doesn't exist in the dictionary, removing the need to explicitly check if a key exists before incrementing/decrementing its value.

Time: O(L + Q)Space: O(L)

Trade-offs: It might provide slightly better readability, and can simplify code, but no significant performance differences are expected compared to using collections.Counter.

✨

Key Insights

1Insight 1: Using direct grid representation is not feasible due to potentially huge grid size (up to 10^9). Therefore, storing the state of each cell individually is space inefficient. Hash tables are suitable for storing the states of lit lamps, rows, columns, and diagonals.
2Insight 2: Instead of representing the entire grid, we only need to keep track of the lit lamps and the counts of illuminated rows, columns, and diagonals using hash tables (or counters).
3Insight 3: Efficiently managing the lamps to be turned off after each query is crucial. A set can be used to quickly check and remove lamps that need to be turned off during the query process.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Edge Cases

Edge case 1: Duplicate lamps in the `lamps` array. The `lamp_positions` set prevents adding the same lamp multiple times.
Edge case 2: Queries outside the grid. The provided solutions do not explicitly check for out-of-bounds indices, but the logic works because if a lamp outside the grid existed, its counts would be zero and so will not impact illumination calculations.
Edge case 3: Turning off the same lamp multiple times during neighbor processing. The `lamp_positions` set ensures that each lamp is only turned off once per query, even if it's adjacent to the query cell multiple times.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Using a grid representation. This will lead to memory issues for large values of n.

✗Common mistake 2: Not handling duplicate lamps correctly. Adding a lamp multiple times should only illuminate the grid once.

✗Common mistake 3: Forgetting to turn off adjacent lamps. Ensure all adjacent lamps (including diagonals) are turned off after each query.

✗Common mistake 4: Not using efficient data structures. Using lists instead of sets or hash tables to check for lamp presence will result in Time Limit Exceeded (TLE).

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Resource allocation. Imagine a grid of resources where turning on a resource makes adjacent resources unavailable. Queries can represent requests for resources, and the algorithm helps determine if a request can be fulfilled.

🏦Real-world scenario 2: Sensor networks. A grid of sensors illuminates an area. Queries represent points of interest, and the algorithm determines if the sensor coverage is sufficient. Turning off a sensor simulates a sensor failure, and the algorithm recalculates the coverage.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

These problems test your ability to optimize. Start with a brute force solution, then improve.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 10, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 14

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 7

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 30

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

Is it okay to not fully solve hard problems in interviews?

Yes! Interviewers care more about your problem-solving process than the final answer. Demonstrate: clear communication, systematic approach, ability to recognize when to pivot strategies, and graceful handling of hints. Partial progress with good reasoning is valued.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Grid Illumination"?

For this hard-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?