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

Unique Paths III

Difficulty: Hard

Problem Description

You are given an m x n integer array grid where grid[i][j] could be:

  • 1 representing the starting square. There is exactly one starting square.
  • 2 representing the ending square. There is exactly one ending square.
  • 0 representing empty squares we can walk over.
  • -1 representing obstacles that we cannot walk over. Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

Key Insights

  • The problem can be solved using backtracking to explore all possible paths.
  • We must keep track of the number of non-obstacle squares that need to be visited.
  • Recursive exploration allows us to navigate through valid squares while avoiding obstacles.
  • Each valid path must start at the beginning square and end at the ending square, visiting all non-obstacle squares exactly once.

Space and Time Complexity

Time Complexity: O(4^(mn)) in the worst case, where m and n are the dimensions of the grid; this accounts for exploring all possible paths. Space Complexity: O(mn) for the recursion stack and visited state.

Solution

The solution employs a backtracking approach. We start from the given starting square and recursively explore all four possible directions (up, down, left, right). During exploration, we keep track of:

  • The number of steps taken.
  • The number of squares visited.
  • A visited matrix to ensure we do not revisit squares.

Once we reach the ending square, we check if all non-obstacle squares have been visited. If they have, we count this as a valid path. This process continues until all possibilities are exhausted.

Code Solutions

def uniquePathsIII(grid):
    rows, cols = len(grid), len(grid[0])
    start_x = start_y = end_x = end_y = empty_count = 0

    # Find the start, end positions and count empty squares
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1:
                start_x, start_y = r, c
            elif grid[r][c] == 2:
                end_x, end_y = r, c
            if grid[r][c] == 0:
                empty_count += 1

    # Directions for moving in 4 possible ways
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    visited = set()

    def backtrack(x, y, count):
        # If we reach the end and visited all empty squares
        if (x, y) == (end_x, end_y):
            return 1 if count == empty_count else 0
        
        # Mark the square as visited
        visited.add((x, y))
        paths = 0
        
        # Explore all 4 directions
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and (nx, ny) not in visited and grid[nx][ny] != -1:
                paths += backtrack(nx, ny, count + 1)
        
        # Unmark the square to allow revisiting in other paths
        visited.remove((x, y))
        return paths

    # Start backtracking from the starting position
    return backtrack(start_x, start_y, -1)  # Start with -1 as we haven't counted the start square
← Back to All Questions