LeetCode 1001 - Grid Illumination

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

On a N x N grid of cells, each cell (x, y) with 0 <= x < N and 0 <= y < N has a lamp.

Initially, some number of lamps are on.  lamps[i] tells us the location of the i-th lamp that is on.  Each lamp that is on illuminates every square on its x-axis, y-axis, and both diagonals (similar to a Queen in chess).

For the i-th query queries[i] = (x, y), the answer to the query is 1 if the cell (x, y) is illuminated, else 0.

After each query (x, y) [in the order given by queries], we turn off any lamps that are at cell (x, y) or are adjacent 8-directionally (ie., share a corner or edge with cell (x, y).)

Return an array of answers.  Each value answer[i] should be equal to the answer of the i-th query queries[i].

Example 1:

Input: N = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]
Explanation: 
Before performing the first query we have both lamps [0,0] and [4,4] on.
The grid representing which cells are lit looks like this, where [0,0] is the top left corner, and [4,4] is the bottom right corner:
1 1 1 1 1
1 1 0 0 1
1 0 1 0 1
1 0 0 1 1
1 1 1 1 1
Then the query at [1, 1] returns 1 because the cell is lit.  After this query, the lamp at [0, 0] turns off, and the grid now looks like this:
1 0 0 0 1
0 1 0 0 1
0 0 1 0 1
0 0 0 1 1
1 1 1 1 1
Before performing the second query we have only the lamp [4,4] on.  Now the query at [1,0] returns 0, because the cell is no longer lit. 

Note:

1. 1 <= N <= 10^9
2. 0 <= lamps.length <= 20000
3. 0 <= queries.length <= 20000
4. lamps[i].length == queries[i].length == 2

https://blog.csdn.net/likewind1993/article/details/87998850
给定N的范围从1到10^9，如果直接拍脑门构建NxN大的方阵来对所有数据进行存储有点不太现实，再者，构建好NxN方阵之后，其存着的太多的0并没有太多的意义。因此我们需要构造合适的数据结构对题目中提到的关系进行存储。

关系分析
灯以及其照亮的点，这个关系是双向的，因为我们需要
根据照亮的点判断关哪个灯
关灯后熄灭其被照亮的点
查询的位置与被灯照亮的位置，需要被用来进行查找，因此这里的关系是单向
查询的位置周围8个格与灯的位置，因为在进行一次查询之后，如果周围有灯泡，需要将灯泡熄灭，这个关系也是一个单向的关系
最后，由于一个位置可能被多个灯照亮，因此被照亮的位置与灯存在一对多的关系
数据表示及算法流程
数据表示
在对涉及得到的位置信息进行分析之后，我们可以构造相应的数据结构来对以上的数据建立联系。

map<pair<int, int>, int > point_frep, 用map来建立从被照亮的点与灯的关系，**pair<int, int>**是被照亮的位置，后面的int 是该位置上的灯泡数。
map<int, int>x_frep, 表示x行被照亮，第二个int表示被几个灯光照亮
map<int, int>y_frep,表示y列被照亮，第二个int表示被几个灯光照亮
map<int, int>sum_frep, map<int, int> diff_frep分别表示斜着的x + y，x-y行被照亮，第二个int表示被几个灯光照亮。
关于第四个关系可以由以下的图简短说明：

当灯的位置处于（0,2）时可以发现

1. 被照亮的绿色位置的值均满足（x+y = 2）
2. 被照亮的红色位置的值均满足（x- y = -2）
3.
1
2
3
因此，可以很方便的根据给出点的坐标来判断是否被某灯照亮。（其实是分别处于x+y=a, x-y=b直线上）


流程
先对lamps进行遍历，构造提到的灯与被照亮位置的关系
记录每个位置灯的数量
更新其照亮的位置
遍历queries
根据其坐标判断是否被照亮
周围8个格子是否存在灯泡，根据point_frep来判断其值，如果存在灯泡
“熄灭”被照亮的行、列
该位置灯泡数减一
https://leetcode.com/problems/grid-illumination/discuss/243076/Java-Clean-Code-O(N)-Time-and-O(N)-Space-Beats-100

• 
  The row, column or diagonal will remain illuminated if there are > 0 lamps on that particular row, column or diagonal
• all the diagonals with slope= 1, can be represented by x= y+c i.e. they have x-y = constant
• all the diagonals with slope= -1, can be represented by x= -y+c i.e they have x+y = constant
• store the counts in separate maps
• When a lamp is turned off, the count of lamps in respective row, column or diagonal decreases by 1

class Solution {
    int[][] dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}, {1,1}, {1,-1}, {-1,1}, {-1,-1}, {0,0}};
    
 public int[] gridIllumination(int N, int[][] lamps, int[][] queries) {
        Map<Integer, Integer> m1 = new HashMap();       // row number to count of lamps
        Map<Integer, Integer> m2 = new HashMap();       // col number to count of lamps
        Map<Integer, Integer> m3 = new HashMap();       // diagonal x-y to count of lamps
        Map<Integer, Integer> m4 = new HashMap();       // diagonal x+y to count of lamps
        Map<Integer, Boolean> m5 = new HashMap();       // whether lamp is  ON|OFF
        
        // increment counters while adding lamps
        for(int i=0; i<lamps.length; i++){
            int x = lamps[i][0];
            int y = lamps[i][1];
            m1.put(x, m1.getOrDefault(x, 0) + 1);
            m2.put(y, m2.getOrDefault(y, 0) + 1);
            m3.put(x-y, m3.getOrDefault(x-y, 0) + 1);
            m4.put(x+y, m4.getOrDefault(x+y, 0) + 1);
            m5.put(N*x + y, true);
        }

        int[] ans = new int[queries.length];
        // address queries
        for(int i=0; i<queries.length; i++){
            int x = queries[i][0];
            int y = queries[i][1];
            
            ans[i] = (m1.getOrDefault(x, 0) > 0 || m2.getOrDefault(y, 0) > 0 || m3.getOrDefault(x-y, 0) > 0 || m4.getOrDefault(x+y, 0) > 0) ? 1 : 0;            
            // switch off the lamps, if any
            for(int d=0; d<dirs.length; d++){
                int x1 = x + dirs[d][0];
                int y1 = y + dirs[d][1];
    if(m5.containsKey(N*x1 + y1) && m5.get(N*x1 + y1)){
                    // the lamp is on, turn it off, so decrement the count of the lamps
                    m1.put(x1, m1.getOrDefault(x1, 1) - 1);
                    m2.put(y1, m2.getOrDefault(y1, 1) - 1);
                    m3.put(x1 - y1, m3.getOrDefault(x1 - y1, 1) - 1);
                    m4.put(x1 + y1, m4.getOrDefault(x1 + y1, 1) - 1);
                    m5.put(N*x1+y1, false);
                }
            }
        }
        
        return ans;
    }
}

Update:

Following redundant code removed, Thanks to j46 for pointing it out!

 // following condition updated
 if(isValid(x1, y1) && m5.containsKey(N*x1 + y1) && m5.get(N*x1 + y1)){
 // removed the function for checking if the co-ordinates are valid, it is taken care by the .containsKey
    private boolean isValid(int x, int y){
        return (x >= 0 && x < MAX && y>=0 && y< MAX);    // MAX was class variable equal to N
    }

The exact complexity in terms of number of lamps, L and number of queries, Q is as follows:
Time Complexity: O(L+Q)
Space Complexity: O(L)

https://www.cnblogs.com/lz87/p/10434878.html

https://zxi.mytechroad.com/blog/hashtable/leetcode-1001-grid-illumination/

  vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries) {

    unordered_set<long> s;

    unordered_map<int, int> lx, ly, lp, lq;

    for (const auto& lamp : lamps) {

      const int x = lamp[0];

      const int y = lamp[1];

      s.insert(static_cast<long>(x) << 32 | y);

      ++lx[x];

      ++ly[y];

      ++lp[x + y];

      ++lq[x - y];

    }

    vector<int> ans;

    for (const auto& query : queries) {

      const int x = query[0];

      const int y = query[1];      

      if (lx.count(x) || ly.count(y) || lp.count(x + y) || lq.count(x - y)) {

        ans.push_back(1);      

        for (int tx = x - 1; tx <= x + 1; ++tx)

          for (int ty = y - 1; ty <= y + 1; ++ty) {

            if (tx < 0 || tx >= N || ty < 0 || ty >= N) continue;

            const long key = static_cast<long>(tx) << 32 | ty;

            if (!s.count(key)) continue;

            s.erase(key);

            if (--lx[tx] == 0) lx.erase(tx);

            if (--ly[ty] == 0) ly.erase(ty);

            if (--lp[tx + ty] == 0) lp.erase(tx + ty);

            if (--lq[tx - ty] == 0) lq.erase(tx - ty);

          }

      } else {

        ans.push_back(0);

      }

    }

    return ans;

  }

X. not efficient
http://www.noteanddata.com/leetcode-1001-Grid-Illumination-java-solution-note.html

    static class Position {
        int x;
        int y;
        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
        @Override
        public int hashCode() {
            return Objects.hash(x,y);
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Position position = (Position) o;
            return x == position.x &&
                    y == position.y;
        }       
        public String toString() {
            return "[" + x + "," + y + "]";
        }
    }
    public int[] gridIllumination(int N, int[][] lamps, int[][] queries) {
        Set<Position> lampset = new HashSet<>();
        Map<Integer, Set<Position>> rowMap = new HashMap<>();
        Map<Integer, Set<Position>> colMap = new HashMap<>();
        for(int[] lamp: lamps) {
            Position pos = new Position(lamp[0], lamp[1]);
            lampset.add(pos);
            rowMap.compute(lamp[0], (k,v)-> {
                if(v == null) {
                    Set<Position> set = new HashSet<>();
                    set.add(pos);
                    return set;
                }    
                else {
                    v.add(pos);
                    return v;
                }
            });
            colMap.compute(lamp[1], (k,v)->{
                if(v == null) {
                    Set<Position> set = new HashSet<>();
                    set.add(pos);
                    return set;
                }    
                else {
                    v.add(pos);
                    return v;
                }                
            });
        }
        int[] ret = new int[queries.length];
        
        for(int i = 0; i < queries.length; ++i) {
            if(rowMap.containsKey(queries[i][0])) {
                ret[i] = 1;
            }
            else if(colMap.containsKey(queries[i][1])) {
                ret[i] = 1;
            }
            else {
                for(Position pos: lampset) {
                    if(Math.abs(queries[i][0] - pos.x) == Math.abs(queries[i][1]-pos.y)) {
                        ret[i] = 1;
                        break;
                    }
                }
            }
            for(int p = -1; p <= 1; ++p) {
                for(int q = -1; q <= 1; ++q) {
                    int x = queries[i][0] + p;
                    int y = queries[i][1] + q;
                    
                    Position pos = new Position(x, y);
                    if(lampset.contains(pos)) {
                        lampset.remove(pos);
                        
                        Set<Position> setOnRow = rowMap.get(x);
                        setOnRow.remove(pos);
                        if(setOnRow.size() == 0) {
                            rowMap.remove(x);
                        }
                        
                        Set<Position> setOnCol = colMap.get(y);
                        setOnCol.remove(pos);
                        if(setOnCol.size() == 0) {
                            colMap.remove(y);
                        }
                    }
                }
            }            
        }
        return ret;
    }