Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1022. Unique Paths III

My accepted Python solution to LeetCode problem 1022, Unique Paths III, running in 7ms.

  • Difficulty: Hard
  • Python
  • Runtime 7ms
  • Memory 17.4MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 7ms, memory 17.4MB, accepted 2026-01-02.

python
class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        start = None
        empty_count = 0
        
        # Find start and count empty cells (including start)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    start = (i, j)
                    empty_count += 1
                elif grid[i][j] == 0:
                    empty_count += 1
        
        self.result = 0
        
        def dfs(r, c, remaining):
            if grid[r][c] == 2:
                if remaining == 0:
                    self.result += 1
                return
            
            # Mark as visited
            temp = grid[r][c]
            grid[r][c] = -1
            
            # Explore all 4 directions
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] >= 0:
                    dfs(nr, nc, remaining - 1)
            
            # Backtrack
            grid[r][c] = temp
        
        dfs(start[0], start[1], empty_count)
        return self.result

Source