LeetCode Problem 62: Unique Paths

Introduction #

• We are given a robot that trying to move from the top-left corner to the bottom-right corner of a grid.
• Number of rows m and number of columns n are given.
• The robot is initially located at the top-left corner let’s say position (m, n) of a m x n grid.
• The robot is trying to reach the bottom-right corner of the grid (1, 1).
• The robot can only move either down or right at any point in time.

Visualization of the Problem #

At any point in time, the robot can only move either down or right. Let’s say the robot is located at position (3,2) of a 3 x 2 grid.

• Moving right for example means moving from (3,2) to (3,1).
• Moving down for example means moving from (3,2) to (2,2).

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

• Down –> Down –> Right
• Down –> Right –> Down
• Right –> Down –> Down

We can generalize this recursive tree as shown below.

Top-Down Recursive Approach #

Base Cases #

when the robot reaches the end (1,1) or when the robot is out of bound either x or y is 0.

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

Putting it all together #

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 #

The time complexity of the above solution is O(2^(m+n)) because at each step we have two choices to make either move down or move right. The space complexity is O(m+n) because of the recursive calls.

Top-Down Recursive Approach with Memoization #

Idea #

We can use a map to store the results of the subproblems to avoid recomputation. The key of the map is the current position (x, y) of the robot. The value of the map is the number of unique paths from (x, y) to (1, 1). We need to add the base cases to the memoization function.

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 #

The time complexity of the above solution is O(m*n) because we are storing the results of the subproblems in the map. The space complexity is O(m*n) because of the recursive calls.

Buttom-Up Approach with Tabulation #

Idea #

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

Base Cases #

• When the robot is at the end (1,1) the number of unique paths is 1.
• When the robot is out of bound either x or y is 0 the number of unique paths is 0.

Iterating the Matrix #

• We will iterate the matrix from (1,1) to (m,n).
• At each position (i,j) of the matrix, the number of unique paths is the sum of the number of unique paths from (i-1,j) and (i,j-1).

Drawing the Matrix #

Putting it all together #

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 #

The time complexity of the above solution is O(m*n) because we are iterating the matrix from (1,1) to (m,n). The space complexity is O(m*n) because of the matrix.

Buttom-Up Approach with Tabulation (Memory Optimized) #

Idea #

We can use a 1D array to store the result of a subproblem for each position (x, y) of the robot. Since we only need the result of the previous row to calculate the result of the current row, we can use a 1D array to store the result of the previous row.

Code #

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 #

The time complexity of the above solution is O(m*n) because we are iterating the matrix from (1,1) to (m,n). The space complexity is O(n) because of the 1D array.