We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Obstacle Removal to Reach Corner

Difficulty: Hard

Problem Description

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

Key Insights

  • The problem can be viewed as a pathfinding problem in a weighted grid where the weights are determined by the presence of obstacles.
  • A breadth-first search (BFS) can be employed to explore the grid, treating obstacles as weights that need to be minimized.
  • Using a priority queue (min-heap) allows for efficiently exploring paths with fewer obstacles first.

Space and Time Complexity

Time Complexity: O(m * n * log(m * n)), where m is the number of rows and n is the number of columns, due to the BFS with a priority queue. Space Complexity: O(m * n), for the visited array and the priority queue.

Solution

The problem can be solved using a modified breadth-first search (BFS) approach with a priority queue. The priority queue will help explore paths with the least number of obstacles removed first.

  1. Initialize a min-heap (priority queue) and push the starting point (0, 0) with a cost of 0 (no obstacles removed).
  2. Maintain a visited array to track the minimum obstacles removed to reach each cell.
  3. While the priority queue is not empty:
    • Pop the cell with the least obstacles removed.
    • If the cell is the target (m-1, n-1), return the number of obstacles removed.
    • For each possible move (up, down, left, right), calculate the new position and the new cost (incrementing the cost if moving into an obstacle).
    • If the new position is within bounds and offers a better cost than previously recorded, push it onto the queue.
  4. If the queue is exhausted without reaching the target, return -1 (though the problem guarantees a path exists).

Code Solutions

import heapq

def min_obstacles(grid):
    m, n = len(grid), len(grid[0])
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    min_heap = [(0, 0, 0)]  # (obstacles removed, x, y)
    visited = [[float('inf')] * n for _ in range(m)]
    visited[0][0] = 0

    while min_heap:
        obstacles, x, y = heapq.heappop(min_heap)
        if x == m - 1 and y == n - 1:
            return obstacles

        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n:
                new_obstacles = obstacles + grid[nx][ny]
                if new_obstacles < visited[nx][ny]:
                    visited[nx][ny] = new_obstacles
                    heapq.heappush(min_heap, (new_obstacles, nx, ny))
    
    return -1  # This line will never be reached, but it's here for completeness.
← Back to All Questions