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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shortest Path in a Grid with Obstacles Elimination

Number: 1414

Difficulty: Hard

Paid? No

Companies: Amazon, Bloomberg, Pinterest, TikTok, Google, IMC, Nuro, Meta, Snap, Apple

Problem Description

Given a grid represented by a 2D matrix where each cell is either empty (0) or an obstacle (1), the goal is to find the shortest path from the top-left corner (0,0) to the bottom-right corner (m-1, n-1) while being allowed to eliminate at most k obstacles along the way. If no valid path exists, return -1.

Key Insights

  • Use a Breadth-First Search (BFS) approach to explore the grid level by level.
  • Maintain a state that includes the current position (row and column) and the number of obstacles eliminated so far.
  • Use a 3-dimensional visited data structure (or a 2D array with obstacle elimination count) to avoid reprocessing states that have been reached with fewer eliminations.
  • The BFS ensures that the first time you reach the target, it is via the shortest path.

Space and Time Complexity

Time Complexity: O(m * n * k), where m and n are grid dimensions and k is the maximum obstacles that can be eliminated. Space Complexity: O(m * n * k), due to storing the state (position and obstacles eliminated).

Solution

The solution utilizes a modified BFS that tracks each state as a tuple (row, column, obstaclesEliminated). Starting from (0,0) with 0 obstacles eliminated, we explore all possible moves (up, down, left, right). When moving to an adjacent cell:

  • If the cell is empty, continue without increasing the elimination count.
  • If the cell is an obstacle and you have remaining eliminations (i.e., obstaclesEliminated < k), increase the elimination count. Only states that offer a better (i.e., lower elimination count) path to a cell compared to any previously recorded state are added to the BFS queue. This prevents unnecessary reprocessing and reduces time complexity. When the destination is reached, the current step count from the BFS is returned. If the queue depletes without reaching the destination, the function returns -1.

Code Solutions

from collections import deque

def shortestPath(grid, k):
    # Dimensions of the grid
    rows, cols = len(grid), len(grid[0])
    
    # If k is large enough, we can take a direct Manhattan route
    if k >= rows + cols - 2:
        return rows + cols - 2
    
    # Queue for BFS: each element is (row, col, obstaclesEliminated, steps)
    queue = deque([(0, 0, 0, 0)])
    
    # 3D visited: visited[row][col] stores the smallest number of obstacles eliminated so far
    visited = [[[False] * (k + 1) for _ in range(cols)] for _ in range(rows)]
    visited[0][0][0] = True
    
    # Possible directions: right, left, down, up
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    while queue:
        row, col, eliminated, steps = queue.popleft()
        
        # If reached destination, return the number of steps
        if row == rows - 1 and col == cols - 1:
            return steps
        
        # Explore neighbors in all four directions
        for dr, dc in directions:
            newRow, newCol = row + dr, col + dc
            # Check if new position is inside the grid bounds
            if 0 <= newRow < rows and 0 <= newCol < cols:
                newEliminated = eliminated + grid[newRow][newCol]
                # Only proceed if the new elimination count is within limit and state not visited
                if newEliminated <= k and not visited[newRow][newCol][newEliminated]:
                    visited[newRow][newCol][newEliminated] = True
                    queue.append((newRow, newCol, newEliminated, steps + 1))
    
    # If destination is unreachable, return -1
    return -1

# Example Usage:
print(shortestPath([[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], 1))
← Back to All Questions