Leetcode solution 1036: Escape a Large Maze

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:

1. 0 <= blocked.length <= 200
2. blocked[i].length == 2
3. 0 <= blocked[i][j] < 10^6
4. source.length == target.length == 2
5. 0 <= source[i][j], target[i][j] < 10^6
6. source != target

Hints

• 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?

Problem link

 

Video Tutorial

You can find the detailed video tutorial here

• Youtube 
• B站

Thought 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 grid
Space 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

 

References

• Leetcode discussion using BFS steps 
• Leetcode discussion using BFS area