Problem statement

https://leetcode.com/problems/grid-illumination/

Solution

For each lamp calculate index of vertical line, horizontal line and both diagonal lines. Keep 4 counters to check how many turned on lamps we have on each of 4 types of lines.

First step is to traverse set of lamps, and update counters. Note, that in original lamps some lamps can be repeated, so we need to traverse set, not list. Then we traverse queries and check if we have lamp on one of the 4 lines, then check cell and 8 neighbors and if we have turned on lamps, we turn them of, and update counters.

Complexity

Time complexity is O(Q + L), where Q is length of queries and L is length of lamps. Space complexity is the same.

Code

class Solution:
    def gridIllumination(self, N, lamps, queries):
        set_lamps = {(i, j) for i, j in lamps}
        c = [Counter() for _ in range(4)]
        
        def update(x, y, d):
            c[0][x] += d
            c[1][y] += d
            c[2][x+y] += d
            c[3][x-y] += d
          
        for i, j in set_lamps: update(i, j, 1)
            
        ans = []
            
        for x, y in queries:
            ans.append(c[0][x] >= 1 or c[1][y] >= 1 or c[2][x+y] >= 1 or c[3][x-y] >= 1)
            for dx, dy in product([-1,0,1],[-1,0,1]):
                if (x+dx, y+dy) in set_lamps:
                    update(x+dx, y+dy, -1)
                    set_lamps.remove((x+dx, y+dy))
                
        return [int(i) for i in ans]