You are given a 0-indexed 2D integer array grid of size m x n. Each cell has one of two values:
0 represents an empty cell,1 represents an obstacle that may be removed.You can move up, down, left, or right from and to an empty cell.
Return the minimum number of obstacles to remove so you can move from the upper left corner (0, 0) to the lower right corner (m - 1, n - 1).
Example 1:
Input: grid = [[0,1,1],[1,1,0],[1,1,0]] Output: 2 Explanation: We can remove the obstacles at (0, 1) and (0, 2) to create a path from (0, 0) to (2, 2). It can be shown that we need to remove at least 2 obstacles, so we return 2. Note that there may be other ways to remove 2 obstacles to create a path.
Example 2:
Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]] Output: 0 Explanation: We can move from (0, 0) to (2, 4) without removing any obstacles, so we return 0.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 1052 <= m * n <= 105grid[i][j] is either 0 or 1.grid[0][0] == grid[m - 1][n - 1] == 0This approach uses a priority queue (or deque) to implement a modified Dijkstra's algorithm to explore the grid in a way similar to the 0-1 BFS (Breadth-First Search). Here, obstacles count as 'cost', and we try to find the minimum 'cost' path from the top-left corner to the bottom-right corner. We assign a priority based on the number of obstacles removed.
The function initiates a deque with the starting point (0, 0). We use a distance array to store the minimum number of obstacles needed to reach each cell. Using directions for the four possible moves, we attempt moving to adjacent cells, leveraging the property of a deque to prioritize uncosted moves (moves to a 0) via appendleft. In contrast, costly moves (moves to a 1) are added normally with append. The algorithm continues until the target cell is reached with the minimum obstacle count possible.
C++
C
Java
C#
JavaScript
Time Complexity: O(m * n)
Space Complexity: O(m * n)
In this approach, we utilize dynamic programming combined with a monotonic queue to solve the problem of reaching the bottom-right corner with minimal obstacle removal. This alternative method involves leveraging the properties of dynamic arrays to store and update minimal removal costs dynamically while using a queue to maintain an effective processing order based on current state values.
This dynamic programming version utilizes a monotonic queue to keep the process smooth, in essence maintaining timeline-line transitions amidst evolved states. Adjustments are made based on evaluated costs for obstacles, ensuring ultimately reaching the target state with minimal burdensome path choices.
C++
Java
C#
Time Complexity: O(m * n)
Space Complexity: O(m * n)
| Approach | Complexity |
|---|---|
| Approach 1: Dijkstra-like Algorithm | Time Complexity: O(m * n) |
| Approach 2: Dynamic Programming with Monotonic Queue | Time Complexity: O(m * n) |
Minimum Obstacle Removal to Reach Corner - Leetcode 2290 - Python • NeetCodeIO • 7,280 views views
Watch 9 more video solutions →Practice Minimum Obstacle Removal to Reach Corner with our built-in code editor and test cases.
Practice on FleetCode