Overview
In the standard approach, we use an entire 2D matrix. But notice that `dp[r][c]` only relies on `dp[r-1][c]` (directly above) and `dp[r][c-1]` (directly to the left).
Loading...
Loading...
Loading Curriculum...
Loading Subject...
Loading Topic...
Loading Lesson...
Loading Lab...
Explore how to aggressively optimize the Space Complexity of the Unique Paths II algorithm from O(M * N) down to just O(N).
In the standard approach, we use an entire 2D matrix. But notice that `dp[r][c]` only relies on `dp[r-1][c]` (directly above) and `dp[r][c-1]` (directly to the left).
We can use a 1D array of size N (number of columns). Before we update `dp[c]`, it holds the value from the row above (`dp[r-1][c]`). Once we add `dp[c-1]` to it, it becomes the new value for the current row!
If we encounter an obstacle in the grid, we simply set `dp[c] = 0`. This properly blocks any paths that would have come from above, and stops it from contributing to cells on the right.
For the first column (`c = 0`), there is no `dp[c-1]`. We just keep `dp[0]` as it was, unless there is an obstacle, in which case we set it to 0 forever.