Minimum Obstacle Removal to Reach Corner - Practice Coding Problems

Minimum Obstacle Removal to Reach Corner - Problem

Array Breadth-First Search Graph Heap (Priority Queue) Matrix Shortest Path Hard

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).

Input & Output

Example 1 — Basic Case

$ Input: grid = [[0,1,1],[1,1,0],[1,1,0]]

› Output: 2

💡 Note: We can remove the obstacles at (0,1) and (0,2) to create path (0,0) → (0,1) → (0,2) → (1,2) → (2,2)

Example 2 — No Obstacles Needed

$ Input: grid = [[0,1,0,0,0],[1,1,0,1,0],[0,0,0,1,0]]

› Output: 0

💡 Note: Path exists without removing obstacles: (0,0) → (0,2) → (0,3) → (0,4) → (1,4) → (2,4)

Example 3 — Minimum Grid

$ Input: grid = [[0,0],[0,0]]

› Output: 0

💡 Note: Simple path from (0,0) → (0,1) → (1,1) with no obstacles

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 10⁵
2 ≤ m * n ≤ 10⁵
grid[i][j] is either 0 or 1
grid[0][0] == grid[m - 1][n - 1] == 0

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2D grid with 0s (empty) and 1s (obstacles)

Find Path

Navigate from top-left to bottom-right

Count Removals

Return minimum obstacles removed

Key Takeaway

🎯 Key Insight: Use 0-1 BFS to prioritize free moves over obstacle removals for optimal pathfinding

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Meta 28

The key insight is to treat this as a shortest path problem where moving through empty cells costs 0 and removing obstacles costs 1. The optimal approach uses 0-1 BFS with deque to prioritize free moves over obstacle removals. Time: O(m*n), Space: O(m*n)

Common Approaches

Approach	Time	Space	Notes
✓ Standard BFS	O(mn2^(m*n))	O(mn2^k)	Use breadth-first search to explore paths level by level, tracking obstacles removed
0-1 BFS with Deque	O(m*n)	O(m*n)	Use 0-1 BFS with deque to prioritize moves through empty cells over obstacle removal
DFS with Backtracking	O(4^(m*n))	O(m*n)	Explore all possible paths using recursive DFS and track minimum obstacles removed

Standard BFS — Algorithm Steps

Start BFS from (0,0) with obstacles = 0
For each position, explore 4 directions
Track obstacles removed for each path
Return obstacles when reaching destination

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Queue

Start with (0,0) in queue

Process Level

Explore all 4 directions from each position

Track States

Keep track of position and obstacles removed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_QUEUE 100000

struct State {
    int row, col, obstacles;
};

int solution(int** grid, int gridSize, int* gridColSize) {
    int m = gridSize, n = gridColSize[0];
    struct State queue[MAX_QUEUE];
    int visited[1000][1000][100];
    memset(visited, 0, sizeof(visited));
    
    int front = 0, rear = 0;
    queue[rear++] = (struct State){0, 0, grid[0][0]};
    
    while (front < rear) {
        struct State curr = queue[front++];
        
        if (curr.row == m - 1 && curr.col == n - 1) {
            return curr.obstacles;
        }
        
        if (curr.obstacles < 100 && visited[curr.row][curr.col][curr.obstacles]) continue;
        if (curr.obstacles < 100) visited[curr.row][curr.col][curr.obstacles] = 1;
        
        int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (int i = 0; i < 4; i++) {
            int nr = curr.row + directions[i][0];
            int nc = curr.col + directions[i][1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n) {
                int newObstacles = curr.obstacles + grid[nr][nc];
                if (newObstacles < 100 && !visited[nr][nc][newObstacles]) {
                    queue[rear++] = (struct State){nr, nc, newObstacles};
                }
            }
        }
    }
    
    return -1;
}

int main() {
    // Simple test case
    int testGrid[3][3] = {{0,1,1},{1,1,0},{1,1,0}};
    int* gridRows[3];
    int colSizes[3] = {3, 3, 3};
    
    for (int i = 0; i < 3; i++) {
        gridRows[i] = testGrid[i];
    }
    
    printf("%d\n", solution(gridRows, 3, colSizes));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m*n*2^(m*n))

May visit each cell multiple times with different obstacle counts

✓ Linear Growth

Space Complexity

O(m*n*2^k)

Queue stores positions with different obstacle removal counts

⚡ Linearithmic Space

68.0K Views

High Frequency

~35 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Standard BFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler