Grid Illumination - Practice Coding Problems

Grid Illumination - Problem

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, col_j]. For the j-th query, determine whether grid[row_j][col_j] is illuminated or not. After answering the j-th query, turn off the lamp at grid[row_j][col_j] and its 8 adjacent lamps if they exist. A lamp is adjacent if its cell shares either a side or corner with grid[row_j][col_j].

Return an array of integers ans, where ans[j] should be 1 if the cell in the j-th query was illuminated, or 0 if the lamp was not.

Input & Output

Example 1 — Basic Illumination

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

› Output: [1,0]

💡 Note: Query [1,1]: Lamp at [0,0] illuminates same main diagonal (0-0 = 1-1). Query [1,0]: Lamp at [0,0] illuminates same column 0, but after first query, nearby lamps are turned off.

Example 2 — Multiple Lamps

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

› Output: [1,1]

💡 Note: First query [1,1]: Both lamps illuminate this position. Second query [1,1]: Lamps were turned off in 3x3 area, but lamp at [4,4] is still active and illuminates via diagonal.

Example 3 — No Illumination

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

› Output: [0]

💡 Note: Query [4,4]: Lamp at [0,0] does not illuminate [4,4] (different row, column, and diagonals).

Constraints

1 ≤ n ≤ 10⁹
0 ≤ lamps.length ≤ 20000
0 ≤ queries.length ≤ 20000
lamps[i].length == 2
0 ≤ row_i, col_i < n

Visualization

Tap to expand

Understanding the Visualization

Input

Grid with lamps at specific positions

Illumination

Each lamp lights up its row, column, and diagonals

Query & Turn Off

Check illumination, then turn off nearby lamps

Key Takeaway

🎯 Key Insight: Use hash maps to count illuminating lines (rows/columns/diagonals) for O(1) query time

Asked in

G Google 15 a Amazon 8 M Microsoft 6

The key insight is to use hash maps to count illuminating lines instead of checking individual lamps. Track counts for rows, columns, and both diagonals. A cell is illuminated if any of its lines has count > 0. Best approach uses hash maps with Time: O(l + q), Space: O(l).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(q × l)	O(l)	For each query, check all lamps to see if any illuminates the cell
Hash Map Optimization	O(l + q)	O(l)	Use hash maps to count illuminating lines instead of checking individual lamps

Brute Force — Algorithm Steps

Step 1: For each query, iterate through all active lamps
Step 2: Check if lamp illuminates query cell (same row/column/diagonal)
Step 3: Remove lamps in 3x3 area around query position

Visualization

Tap to expand

Step-by-Step Walkthrough

Query Cell

Check if position (1,1) is illuminated

Check All Lamps

Iterate through all lamps, check row/column/diagonal

Turn Off Nearby

Remove lamps in 3x3 area around query

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_LAMPS 20000
#define MAX_QUERIES 20000

typedef struct {
    int r, c;
} Lamp;

int* solution(int n, Lamp* lamps, int lampsSize, int queries[][2], int queriesSize, int* returnSize) {
    int* result = malloc(queriesSize * sizeof(int));
    *returnSize = queriesSize;
    bool* active = malloc(lampsSize * sizeof(bool));
    
    // Initialize all lamps as active
    for (int i = 0; i < lampsSize; i++) {
        active[i] = true;
    }
    
    for (int q = 0; q < queriesSize; q++) {
        int qr = queries[q][0], qc = queries[q][1];
        bool illuminated = false;
        
        // Check if any active lamp illuminates this position
        for (int i = 0; i < lampsSize; i++) {
            if (!active[i]) continue;
            int lr = lamps[i].r, lc = lamps[i].c;
            // Same row, column, or diagonal
            if (lr == qr || lc == qc || lr - lc == qr - qc || lr + lc == qr + qc) {
                illuminated = true;
                break;
            }
        }
        
        result[q] = illuminated ? 1 : 0;
        
        // Turn off lamps in 3x3 area around query
        for (int i = 0; i < lampsSize; i++) {
            if (!active[i]) continue;
            int lr = lamps[i].r, lc = lamps[i].c;
            if (abs(lr - qr) <= 1 && abs(lc - qc) <= 1) {
                active[i] = false;
            }
        }
    }
    
    free(active);
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[100000];
    scanf(" %[^\n]", line);
    
    Lamp lamps[MAX_LAMPS];
    int lampsSize = 0;
    
    // Parse lamps array
    char* ptr = line + 1; // Skip opening bracket
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            int r = 0, c = 0;
            while (*ptr && *ptr != ',') {
                r = r * 10 + (*ptr - '0');
                ptr++;
            }
            ptr++; // Skip comma
            while (*ptr && *ptr != ']') {
                c = c * 10 + (*ptr - '0');
                ptr++;
            }
            lamps[lampsSize].r = r;
            lamps[lampsSize].c = c;
            lampsSize++;
            ptr++; // Skip closing bracket
        }
        if (*ptr == ',') ptr++;
    }
    
    scanf(" %[^\n]", line);
    int queries[MAX_QUERIES][2];
    int queriesSize = 0;
    
    // Parse queries array
    ptr = line + 1; // Skip opening bracket
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            int r = 0, c = 0;
            while (*ptr && *ptr != ',') {
                r = r * 10 + (*ptr - '0');
                ptr++;
            }
            ptr++; // Skip comma
            while (*ptr && *ptr != ']') {
                c = c * 10 + (*ptr - '0');
                ptr++;
            }
            queries[queriesSize][0] = r;
            queries[queriesSize][1] = c;
            queriesSize++;
            ptr++; // Skip closing bracket
        }
        if (*ptr == ',') ptr++;
    }
    
    int returnSize;
    int* result = solution(n, lamps, lampsSize, queries, queriesSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(q × l)

For each query, we check all lamps to see if they illuminate the cell

✓ Linear Growth

Space Complexity

O(l)

Store the set of active lamps

✓ Linear Space

25.0K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler