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

Unique Paths III

Number: 1022

Difficulty: Hard

Paid? No

Companies: Amazon, Meta, Google, Pinterest, Cruise, Bloomberg

Problem Description

Given an m x n grid where:

  • 1 represents the starting square.
  • 2 represents the ending square.
  • 0 represents empty squares that can be walked over.
  • -1 represents obstacles. Return the number of 4-directional paths from the start to the end that visit every non-obstacle square exactly once.

Key Insights

  • Count all non-obstacle cells (including start and end) to know the route length required.
  • Use Depth First Search (DFS) to explore all possible paths from the starting cell.
  • Mark cells as visited during recursion to avoid revisiting and backtrack afterwards.
  • Only count a path when reaching the ending cell and the number of visited cells equals the total non-obstacle count.

Space and Time Complexity

Time Complexity: O(3^(mn)) in the worst-case scenario due to branching factor in DFS. Space Complexity: O(mn) due to recursion call stack and in-place modifications of the grid.

Solution

We solve the problem by performing a DFS starting from the unique starting cell. Before DFS, count the total number of non-obstacle cells. As DFS explores neighbors recursively, mark the cell as visited (by setting it to -1) to prevent cycles and restore its value after exploring (backtracking). When the ending cell is reached, check if we have visited all non-obstacle cells. If yes, increment the valid path count.

Data structures and algorithms used:

  • Recursion (DFS) for exploring all valid paths.
  • In-place grid marking for tracking visited cells.
  • Backtracking for restoring grid state. This approach ensures that every possible valid route is considered while correctly handling obstacles and ensuring each non-obstacle cell is visited exactly once.

Code Solutions

def uniquePathsIII(grid):
    # Get the dimensions of the grid
    rows, cols = len(grid), len(grid[0])
    empty = 0
    start = None
    
    # Count the number of non-obstacle cells and locate the starting cell
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] != -1:
                empty += 1
            if grid[i][j] == 1:
                start = (i, j)
                
    paths = 0
    # DFS helper to explore the grid
    def dfs(i, j, count):
        nonlocal paths
        # When the ending cell is reached, check if all non-obstacle cells are visited
        if grid[i][j] == 2:
            if count == empty:
                paths += 1
            return
        
        # Mark the current cell as visited by setting it as an obstacle
        temp = grid[i][j]
        grid[i][j] = -1
        
        # Explore all four directions
        for di, dj in [(1,0), (-1,0), (0,1), (0,-1)]:
            new_i, new_j = i + di, j + dj
            if 0 <= new_i < rows and 0 <= new_j < cols and grid[new_i][new_j] != -1:
                dfs(new_i, new_j, count + 1)
                
        # Backtrack: restore the original cell value
        grid[i][j] = temp
        
    # Start the DFS from the starting point with a count of 1
    dfs(start[0], start[1], 1)
    return paths

# Example usage:
if __name__ == '__main__':
    grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
    print(uniquePathsIII(grid))  # Expected output: 2
← Back to All Questions