Unique Paths III

Hard

Amazon

1 view

Topics:

RecursionGraphs

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.

For example:

grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]

The expected output is 2.

Explanation: We have the following two paths:

(0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
(0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

Another example:

grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]

The expected output is 4.

Explanation: We have the following four paths:

(0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
(0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
(0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
(0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

Can you provide an efficient solution to count the number of unique paths?

Unique Paths III

Hard

Amazon

1 view

Topics:

RecursionGraphs

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.

For example:

grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]

The expected output is 2.

Explanation: We have the following two paths:

(0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
(0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

Another example:

grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]

The expected output is 4.

Explanation: We have the following four paths:

(0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
(0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
(0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
(0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

Can you provide an efficient solution to count the number of unique paths?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the grid (number of rows and columns), and what are the constraints on these dimensions?
What integer values are possible in the grid, and what do the values -1, 0, 1, and 2 specifically represent in terms of path traversal?
Is there always a starting point (value '1') and an ending point (value '2') present in the grid, and are they guaranteed to be unique?
If there is no valid path that visits every non-obstacle square exactly once, what should I return?
Is diagonal movement allowed, or can I only move up, down, left, and right?

Brute Force Solution

Approach

The brute force approach is like exploring every possible route in a maze. We'll try going in every direction from the starting point, one step at a time, until we either find the exit or hit a dead end.

Here's how the algorithm would work step-by-step:

Start at the marked starting location in the grid.
From the current location, explore each possible direction you can move: up, down, left, and right.
Before moving, check if the new location is within the boundaries of the grid and is not an obstacle.
If a move is valid, mark the new location as visited and move to it.
Repeat this process from the new location, exploring all valid directions again.
If you reach the end location after visiting all empty locations exactly once, count it as a successful path.
If you reach a dead end (no valid moves) or visit the end location without visiting all empty locations, backtrack and try a different path.
Continue exploring all possible paths until you have exhausted all possibilities, keeping a count of all successful paths.

Code Implementation

def unique_paths_iii_brute_force(grid):
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])
    start_row, start_column = -1, -1
    empty_cells_count = 0

    for row in range(number_of_rows):
        for column in range(number_of_columns):
            if grid[row][column] == 1:
                start_row, start_column = row, column
            if grid[row][column] == 0:
                empty_cells_count += 1

    path_count = 0

    def explore_paths(row, column, visited_cells):
        nonlocal path_count

        # Check boundaries and obstacles.
        if row < 0 or row >= number_of_rows or column < 0 or column >= number_of_columns or grid[row][column] == -1:
            return

        # If we reached the end.
        if grid[row][column] == 2:
            # Ensure all empty cells are visited.
            if visited_cells == empty_cells_count + 1:
                path_count += 1
            return

        # Mark current cell as visited
        grid[row][column] = -1
        
        # Recursively explore all possible paths
        explore_paths(row + 1, column, visited_cells + 1)

        explore_paths(row - 1, column, visited_cells + 1)

        explore_paths(row, column + 1, visited_cells + 1)

        explore_paths(row, column - 1, visited_cells + 1)

        # Backtrack: Restore cell value for other paths.
        grid[row][column] = 0 if grid[row][column] != 1 else 1

    explore_paths(start_row, start_column, 0)
    
    return path_count

Big(O) Analysis

Time Complexity

O(4^(r*c)) – The brute force approach explores all possible paths from the starting point, using recursion. In the worst-case scenario, where most cells are empty, each cell has up to four possible directions to move. The depth of the recursion is bounded by the number of empty cells, which is r * c where r is the number of rows and c is the number of columns in the grid. Therefore, in the worst case, the algorithm explores all possible paths of length r*c, resulting in a time complexity of O(4^(r*c)). The base 4 represents the 4 possible directions (up, down, left, right).

Space Complexity

O(R * C) – The space complexity is dominated by the recursion stack. In the worst-case scenario, the algorithm might explore a path that visits almost every cell in the grid before backtracking. The maximum depth of the recursion can be proportional to the number of cells in the grid. Therefore, the maximum size of the call stack will be proportional to the number of rows (R) times the number of columns (C) in the grid, as each recursive call adds a new frame to the stack storing local variables and the return address. The 'visited' status could also be represented using an auxiliary grid of the same size as the input grid, further contributing to the R * C space requirement. Hence the space complexity is O(R * C).

Optimal Solution

Approach

The core idea is to explore every possible path while ensuring we visit every empty square exactly once. To avoid re-exploring the same squares, we use a technique that marks squares as visited during our exploration and unmarks them when we backtrack.

Here's how the algorithm would work step-by-step:

Start at the starting square.
Count the number of empty squares (including the start but not the end).
From the current square, explore each of the four possible directions (up, down, left, right).
Before moving to a new square, check if it's within the grid boundaries, not an obstacle, and not already visited.
If a valid square is found, mark it as visited, and reduce the empty square count by one.
Move to this new square and repeat the exploration.
If you reach the end square and all empty squares have been visited (count is zero), increment the path counter.
After exploring all directions from a square, backtrack. Unmark the square as visited and increase the empty square count by one. This allows other paths to explore this square.
The total number of valid paths is the final count of paths where you reach the end and have visited all empty squares exactly once.

Code Implementation

def uniquePathsIII(grid):    rows = len(grid)
    columns = len(grid[0])
    start_row, start_column = 0, 0
    empty_squares = 1

    for row in range(rows):
        for column in range(columns):
            if grid[row][column] == 1:
                start_row, start_column = row, column
            elif grid[row][column] == 0:
                empty_squares += 1

    path_count = 0

    def depthFirstSearch(row, column, remaining_empty_squares):
        nonlocal path_count

        # Reached the destination and visited all empty cells
        if grid[row][column] == 2 and remaining_empty_squares == 0:
            path_count += 1
            return

        # Possible movements
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        for delta_row, delta_column in directions:
            new_row = row + delta_row
            new_column = column + delta_column

            # Bounds and obstacle check
            if 0 <= new_row < rows and 0 <= new_column < columns and \
               grid[new_row][new_column] >= 0:

                # Mark as visited.
                grid[new_row][new_column] = -2

                depthFirstSearch(new_row, new_column, remaining_empty_squares - 1)

                # Backtrack, unmark the square
                grid[new_row][new_column] = 0

    # Initiate the search
    grid[start_row][start_column] = -2
    # Start dfs from starting point
    depthFirstSearch(start_row, start_column, empty_squares)
    return path_count

Big(O) Analysis

Time Complexity

O(4^(m*n)) – The algorithm explores all possible paths on the grid using a recursive depth-first search. In the worst-case scenario, each empty cell has up to four possible directions to explore. The number of empty cells is at most the total number of cells in the grid, which is m * n, where m and n are the dimensions of the grid. Thus, in the worst case, the algorithm explores approximately 4^(m*n) paths. Therefore, the time complexity is O(4^(m*n)).

Space Complexity

O(R*C) – The dominant factor in space complexity is the recursion depth of the depth-first search (DFS). In the worst-case scenario, the algorithm may explore almost every cell in the grid before reaching the end or hitting a dead end. The maximum depth of the recursion, and therefore the space used by the call stack, is proportional to the number of cells in the grid, represented by R rows and C columns. Thus, the space complexity due to the call stack is O(R*C) where R is the number of rows and C is the number of columns in the grid. There are no other significant data structures used.

Edge Cases

Case	How to Handle
Null or empty grid	Return 0 if the grid is null or has zero rows or columns as there are no paths.
Grid with no starting or ending point	Return 0 if the grid doesn't contain exactly one start (1) and one end (2).
Grid with no empty cells (all obstacles)	Return 0 if the number of empty cells plus start and end is not equal to the number of cells visited, since no path exists to visit all cells.
Grid where start and end are adjacent, and all other cells are obstacles	Return 1 if the adjacent cells are obstacles and a path is available, representing the path from start to end.
Maximum grid size (e.g., 20x20) leading to deep recursion	Ensure the solution uses a backtracking approach with pruning or optimization to avoid stack overflow errors by caching the visited cells.
Grid with only one possible path	Verify that the solution correctly finds the single unique path when it exists, ensuring the logic handles cases with only one valid route.
Integer overflow when calculating the number of empty cells if grid is very large.	Use a data type with a larger range, like long, to store the count of empty cells if the grid size is significantly large.
Multiple starting or ending points in the grid	Return 0 if more than one starting (1) or ending point (2) exists in the grid, since the problem specifies exactly one of each.