Unique Paths III Solution in Java

Explore More Solutions:

Unique Paths III in C++
Unique Paths III in Python


class Solution {
  public int uniquePathsIII(int[][] grid) {
    int empty = 1;
    int sx = -1;
    int sy = -1;
    int ex = -1;
    int ey = -1;

    for (int i = 0; i < grid.length; ++i)
      for (int j = 0; j < grid[0].length; ++j)
        if (grid[i][j] == 0) {
          ++empty;
        } else if (grid[i][j] == 1) {
          sx = i;
          sy = j;
        } else if (grid[i][j] == 2) {
          ex = i;
          ey = j;
        }

    dfs(grid, empty, sx, sy, ex, ey);

    return ans;
  }

  private int ans = 0;

  private void dfs(int[][] grid, int empty, int i, int j, int ex, int ey) {
    if (i < 0 || i == grid.length || j < 0 || j == grid[0].length)
      return;
    if (grid[i][j] < 0)
      return;
    if (i == ex && j == ey) {
      if (empty == 0)
        ++ans;
      return;
    }

    grid[i][j] = -2;
    dfs(grid, empty - 1, i + 1, j, ex, ey);
    dfs(grid, empty - 1, i - 1, j, ex, ey);
    dfs(grid, empty - 1, i, j + 1, ex, ey);
    dfs(grid, empty - 1, i, j - 1, ex, ey);
    grid[i][j] = 0;
  }
}

Problem Description

Welcome to the world of Unique Paths III, where you get to play the role of a brave little robot trying to navigate a grid filled with obstacles, starting points, and endpoints. Imagine you’re on a treasure hunt, but instead of gold coins, you’re collecting empty squares while avoiding the dreaded walls. Your mission, should you choose to accept it, is to find all the unique paths from the starting point to the endpoint, stepping on every empty square exactly once. Sounds easy, right? Well, it’s like trying to walk through a crowded room without stepping on anyone’s toes—good luck with that!

In this problem, you are given a grid represented by a 2D array where:

0 represents an empty square,
1 represents the starting point,
2 represents the ending point, and
-1 represents an obstacle.

Your task is to count how many unique paths exist from the starting point to the ending point, stepping on every empty square exactly once.

Approach Explanation

The approach used in this solution is a classic Depth-First Search (DFS) technique. The algorithm starts by counting the number of empty squares and identifying the starting and ending points. It then recursively explores all possible paths from the starting point to the ending point, marking squares as visited by changing their values. When it reaches the endpoint, it checks if all empty squares have been visited. If so, it increments the count of unique paths.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(4^N), where N is the number of empty squares.
Space Complexity	O(N) due to the recursion stack used in the DFS.

Real-World Example

Imagine you’re at a party, and you need to navigate through a maze of people to reach the snack table (the endpoint) while making sure to greet every guest (the empty squares) along the way. You can’t just skip anyone, and if you bump into a wall (obstacle), you’re stuck! The Unique Paths III problem is just like that—finding the best route while making sure you don’t miss anyone.