Problem Statement
In a 1 million by 1 million grid, the coordinates of each grid square are
(x, y) with 0 <= x, y < 10^6.
We start at the
source square and want to reach the target square. Each move, we can walk to a 4-directionally adjacent square in the grid that isn't in the given list of blocked squares.
Return
true if and only if it is possible to reach the target square through a sequence of moves.
Example 1:
Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2] Output: false Explanation: The target square is inaccessible starting from the source square, because we can't walk outside the grid.
Example 2:
Input: blocked = [], source = [0,0], target = [999999,999999] Output: true Explanation: Because there are no blocked cells, it's possible to reach the target square.
Note:
0 <= blocked.length <= 200blocked[i].length == 20 <= blocked[i][j] < 10^6source.length == target.length == 20 <= source[i][j], target[i][j] < 10^6source != target
- If we become stuck, there's either a loop around the source or around the target.
- If there is a loop around say, the source, what is the maximum number of squares it can have?
Video Tutorial
You can find the detailed video tutorial hereThought Process
At first, I am puzzled why this problem would be a hard one. It seems simply applying a BFS would get the answer. So here we go.Brute force, simple BFS
Of course it will hit memory limit because I am allocating a 2-dimensional visited array. Assume boolean is 8 bit -> 1B, 1 Million * 1 Million = 1TB, OMG, immediately using a set instead.P.S. fun fact, you can use this method to test how much memory leetcode allocate to this problem, you can use binary search and memory is around 300MB
However, this would start hitting Time Limit Exception. Now I begin to notice a few constrains, e.g., the block size is only 200 while the grid is 1M*1M. Simply going from source to target worst case would cause a timeout.
Next thought would be does it help if we sort the block array? While we are doing the BFS, if the block is already larger/smaller than the max/min of the block, we can early stop. However, this won't help if we simply place a block near the target. Also, this would be a nightmare to implement.
Check block loops on source and target
Following the two hints, it would be natural to come up with this idea. Given such huge contrast between the block size (0,200) and the grid size (1M, 1M), all we need to do is to check if there is any loops built by block on source and target b/c if there is a loop, we cannot explore outside of the loop. However, notice if target and source are in the same loop, then we are fine.There are two ways to early stop this loop checking. One way is to count the BFS steps, the other way is to follow the hints, given 200 blocks, what's the max area it can cover. Given the length 200, Fig 2 in the below graph can result in the largest area. Therefore, we can early terminate the BFS search once we covered more than 19900 blocks. (We can relax this a bit to 20000, doesn't matter)
- Fig 1 area = 100 * 100 = 10000
- Fig 2 area = 1 + 2 + 3 + ... + 199 = (1+199)*199/2 = 19900
- Fig 3 area = 1 * 200 = 200
- Fig 4 area = 790 (2*Pi*R = 100, thus R = 15.92, Pi * R^2 = 790 )
Solutions
Brute force, simple BFS
Time Complexity: O(N), N = 1M * 1M, essentially need to cover the entire huge gridSpace Complexity: O(N), N = 1M*1M, essentially all the nodes need to be put to visited set
Check block loops on source and target
Time Complexity: O(N), N in terms of block size
Space Complexity: O(N), N in terms of block size
