LeetCode Problem 62: Unique Paths

Introduction #

In this post, we’ll explore LeetCode Problem 62: Unique Paths, a classic algorithm problem that involves counting the number of possible paths in a grid. We’ll delve into several dynamic programming solutions, ranging from recursive approaches to optimized tabulation methods, all implemented in Go.

Problem Statement #

We are given a robot that is trying to move from the top-left corner to the bottom-right corner of an m x n grid. The robot can only move either down or right at any point in time.

Starting Point: (m, n) (top-left corner of the grid)
Destination: (1, 1) (bottom-right corner of the grid)
Movement Options: Down (x-1, y) or Right (x, y-1)

Our task is to find the number of unique paths the robot can take to reach its destination.

Visualization of the Problem #

Imagine the grid as a matrix where the robot moves from cell to cell. At any given cell (x, y), the robot has two choices:

Move Right: Proceed to (x, y-1)
Move Down: Proceed to (x-1, y)

For example, in a 3 x 2 grid, the robot starts at (3, 2) and aims to reach (1, 1). The possible paths are:

Down ➔ Down ➔ Right
Down ➔ Right ➔ Down
Right ➔ Down ➔ Down

These paths represent all the unique sequences of moves that lead the robot to its goal.

We can generalize this recursive tree as shown below.

Full tree of possible paths from (3,2) to (1,1) is shown below.

Top-Down Recursive Approach #

Concept #

We can think of the problem recursively. The number of unique paths to reach cell (x, y) is the sum of unique paths to reach cell (x-1, y) and cell (x, y-1).

Base Cases #

Destination Reached: When the robot reaches (1, 1), there is exactly one path (the path ending at the destination).
Out of Bounds: If the robot moves beyond the grid boundaries, there are zero paths.

if x == 1 && y == 1 { // base case: reached the end at (1,1)
	return 1
}
if x == 0 || y == 0 { // base case: out of bound
	return 0
}

Recursive Calls #

The robot can move either down or right.
We can recursively call the function with x-1 and y to move down.
We can recursively call the function with x and y-1 to move right.

return fn(x-1, y) + fn(x, y-1) // recursive call: move down or move right

Full Implementation #

func uniquePaths(m int, n int) int {
	var fn func(int, int) int
	fn = func(x int, y int) int {
		if x == 1 && y == 1 { // base case: reached the end
			return 1
		}
		if x == 0 || y == 0 { // base case: out of bound
			return 0
		}
		return fn(x-1, y) + fn(x, y-1) // recursive call: move down or move right
	}
	return fn(m, n)
}

Complexity Analysis #

Time Complexity: O(2^(m+n)), due to the exponential number of recursive calls.
Space Complexity: O(m+n), for the recursion stack depth.

Top-Down Recursive Approach with Memoization #

Concept #

To optimize the recursive solution, we use memoization to store intermediate results and avoid redundant calculations.

Go Implementation #

func uniquePaths(m int, n int) int {
	type key struct {
		x int
		y int
	}
	memo := map[key]int{}

	var fn func(int, int) int
	fn = func(x int, y int) int {
		if val, ok := memo[key{x, y}]; ok {
			return val
		}
		if x == 1 && y == 1 { // base case: reached the end
			return 1
		}
		if x == 0 || y == 0 { // base case: out of bound
			return 0
		}

		ret := fn(x-1, y) + fn(x, y-1) // recursive call: move down or move right
		memo[key{x, y}] = ret

		return ret
	}
	return fn(m, n)
}

Complexity Analysis #

Time Complexity: O(m * n), since each cell’s result is computed once.
Space Complexity: O(m * n), for the memoization map.

Bottom-Up Approach with Tabulation #

Concept #

We can use a matrix to store the result of a subproblem for each position (x, y) of the robot.

Initialization: dp[1][j] = 1 for all j, and dp[i][1] = 1 for all i, since there’s only one way to reach cells in the first row or first column.
Transition: dp[i][j] = dp[i-1][j] + dp[i][j-1]

Go Implementation #

func uniquePaths(m int, n int) int {

	matrix := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		matrix[i] = make([]int, n+1) // initialize the matrix with array of n+1 elements
	}

	matrix[1][1] = 1 // base case when the robot is at the end (1,1)
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if i == 1 && j == 1 { // skip the base case
				continue
			}
			matrix[i][j] = matrix[i-1][j] + matrix[i][j-1]
		}
	}
	return matrix[m][n]

}

Complexity Analysis #

Time Complexity: O(m * n), for filling the table.
Space Complexity: O(m * n), for the DP table.

Bottom-Up Approach with Space Optimization #

Concept #

We can optimize space by using a 1D array since we only need the previous row’s values.

Initialization: dp[j] = 1 for all j
Transition: dp[j] += dp[j-1]

Go Implementation #

func uniquePaths(m int, n int) int {

	arr := make([]int, n)
	for i := range arr {
		arr[i] = 1
	}
	for i := 0; i < m-1; i++ {
		for j := len(arr) - 2; j >= 0; j-- { // iterate the array from right to left
			arr[j] = arr[j] + arr[j+1]
		}
	}
	return arr[0]
}

Complexity Analysis #

Time Complexity: O(m * n), for the nested loops.
Space Complexity: O(n), using a 1D array.

Conclusion #

The Unique Paths problem is a fundamental example that illustrates the essence of dynamic programming. By starting with a simple recursive solution and progressively optimizing it using memoization and tabulation, we can significantly improve efficiency. Understanding these approaches not only helps in solving this problem but also builds a strong foundation for tackling a wide range of algorithmic challenges.