(Medium) 62. Unique Paths, NeetCode 75

https://leetcode.com/problems/unique-paths/description/

Last review: Jun 7, 2025 Next review: 1D DP approach only

DFS (Return-Value)

• Time Complexity O(2^(m * n))
  • Each position has 2 directions
• Space Complexity O(m * n)

func uniquePaths(m int, n int) int {

	directions := [][2]int{[2]int{0, 1}, [2]int{1, 0}}

	// r, c: curuent position
	var dfs func(r, c int) int
	dfs = func(r, c int) int {
		if r == m-1 && c == n-1 {
			return 1
		}
		var ways int
		for _, dir := range directions {
			nr, nc := r+dir[0], c+dir[1]
			if nr >= m || nc >= n {
				continue
			}
			ways += dfs(nr, nc)
		}
		return ways
	}
	return dfs(0, 0)
}

DFS (Return-Value) + 2D DP

• Time Complexity O(m * n)
  • Once it has a cache, it doesn’t revisit a cell.
• Space Complexity O(m * n)

func uniquePaths(m int, n int) int {
	directions := [][2]int{[2]int{0, 1}, [2]int{1, 0}}

	cache := make(map[[2]int]int) // map[(r, c)]ways

	// r, c: curuent position
	var dfs func(r, c int) int
	dfs = func(r, c int) int {
		if r == m-1 && c == n-1 {
			return 1
		}

		key := [2]int{r, c}
		if v, exist := cache[key]; exist {
			return v
		}

		for _, dir := range directions {
			nr, nc := r+dir[0], c+dir[1]
			if nr >= m || nc >= n {
				continue
			}
			cache[key] += dfs(nr, nc)
		}
		return cache[key]
	}

	return dfs(0, 0)
}

2D DP

• Time Complexity O(m * n)
  • Bottom-up doesn’t revisit cells
• Space Complexity O(m * n)

func uniquePaths(m int, n int) int {

	cache := make(map[[2]int]int, m*n) // map[(r, c)]ways

	// last row and last column cells can have 1 way
	for r := 0; r < m; r++ {
		cache[[2]int{r, n - 1}] = 1
	}
	for c := 0; c < n; c++ {
		cache[[2]int{m - 1, c}] = 1
	}

	for r := m - 2; r > -1; r-- {
		for c := n - 2; c > -1; c-- {
			cache[[2]int{r, c}] += cache[[2]int{r + 1, c}]
			cache[[2]int{r, c}] += cache[[2]int{r, c + 1}]
		}
	}

	return cache[[2]int{0, 0}]
}

1D DP ⭐️

Assume m = 3, n = 4

Row 1 (second-last row), we update right-to-left:

Start: dp = [1, 1, 1, 1]

Position Count = (prev row, same col) + (same row, prev col)
               
c = 2:  dp[2] = dp[2] + dp[3] = 1 + 1 = 2
c = 1:  dp[1] = dp[1] + dp[2] = 1 + 2 = 3
c = 0:  dp[0] = dp[0] + dp[1] = 1 + 3 = 4

Now: dp = [4, 3, 2, 1]

Row 0 (top row)