Solution


Approach 1: Backtracking DFS

Intuition and Algorithm

Let's try walking to each 0, leaving an obstacle behind from where we walked. After, we can remove the obstacle.

Given the input limits, this can work because bad paths tend to get stuck quickly and run out of free squares.

Complexity Analysis

  • Time Complexity: , where are the number of rows and columns in the grid. (We can find tighter bounds, but such a bound is beyond the scope of this article.)

  • Space Complexity: .


Approach 2: Dynamic Programming

Intuition and Algorithm

Let dp(r, c, todo) be the number of paths starting from where we are (r, c), and given that todo is the set of empty squares we've yet to walk on.

We can use a similar approach to Approach 1, except we will memoize these states (r, c, todo) so as not to repeat work.

Complexity Analysis

  • Time Complexity: , where are the number of rows and columns in the grid.

  • Space Complexity: .


Analysis written by: @awice.