62. Unique Paths

MediumMathDynamic ProgrammingCombinatorics
Leetcode Link

Problem Description

The problem presents a scenario where we have a m x n grid, and a robot is positioned at the top-left corner of this grid, which is marked by grid[0][0]. The goal for the robot is to reach the bottom-right corner of the grid, designated by grid[m - 1][n - 1]. The robot is restricted to move only in two directions, either down or right, at any given point in time.

The main question is to calculate the total number of unique paths the robot can take to reach from the top-left corner to the bottom-right corner. A path is considered unique if it follows a different sequence of moves. The constraints of the problem ensure that the final answer will be a value that is less than or equal to 2 * 10^9.

Intuition

To approach this problem, we must recognize that it's a classic example of a combinatorial problem that can be solved using dynamic programming (DP). The key insight for a DP solution is that the number of unique paths to reach a particular cell in the grid is the sum of the unique paths to reach the cell directly above it and the cell to its left. This is because the robot can only move down or right, so any path to a cell must come from one of these two adjacent cells.

A recursive solution following this approach would involve a lot of repeated calculations, so a better approach is to use an iterative DP algorithm, which builds up the solution bottom-up and avoids recomputation.

Specifically, we can track the number of ways to reach each cell in a single row as we iterate across the grid. We initialize a list f with a length of n (number of columns) and set all values to 1, because there's only one way to reach any cell in the first row by moving right at every step.

Then, as we iterate row by row starting from the second row, we update each cell's value in the list f with the sum of its own value (the number of paths coming from the left) and the value of the cell before it in the list (the number of paths coming from above). This is done in-place to make the algorithm more space-efficient.

Finally, after we have processed all the rows, the last cell in the list will contain the total number of unique paths to reach the bottom-right cell of the grid.

The uniquePaths function encapsulates this algorithm and returns the number of unique paths as the result.

Learn more about Math, Dynamic Programming and Combinatorics patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Solution Approach

The implementation of the solution employs dynamic programming, which is an algorithmic technique used to solve problems by breaking them down into simpler subproblems. It is especially powerful for problems that involve making a sequence of interrelated decisions, like in this scenario where the robot makes a series of moves either down or to the right.

Here's how dynamic programming is applied in this solution:

  • The use of a one-dimensional array f of size n serves as a space-optimized way to store the number of unique paths to each cell in the current row from the start cell. Initially, this list is initialized with all 1s because in the first row, the robot can only move right, so there's exactly one path to each cell in the row.

    1f = [1] * n

  • We iterate over each additional row in the grid, starting from the second row (since the first row is already initialized). The number of unique paths to reach a cell in the grid at a position [i, j] is equal to the sum of the paths to reach [i, j - 1] and [i - 1, j] (the cell to its left and the cell above it, respectively). Since we are only interested in the current and previous row at any time, we can simply use the same list f to accumulate the count of paths.

    1for _ in range(1, m):
2    for j in range(1, n):
3        f[j] += f[j - 1]

    In the nested loop, each cell f[j] gets updated by adding the value f[j - 1] to it, which effectively means the current value of f[j] corresponds to the cell above [i - 1, j], and f[j - 1] corresponds to the cell to the left [i, j - 1]. By the end of the loop, f[j] will represent the correct number of paths to the cell [i, j].

  • This process is repeated until we have gone through all the rows. As a result, the accumulated number in the last cell of our list f[-1] will indicate the number of unique paths to reach the bottom-right corner of the grid.

    1return f[-1]

The space complexity of this algorithm is O(n), where n is the number of columns in the grid. The time complexity is O(m * n) as every cell gets computed exactly once. By using dynamic programming, this solution efficiently calculates the result without redundancy in computation and with minimal space usage.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

A heap is a ...?

Example Walkthrough

Let's consider a small grid of size 3 x 4 (i.e., m = 3 and n = 4) to illustrate how the solution approach works. For this example, the goal is to determine the number of unique paths from the top-left corner grid[0][0] to the bottom-right corner grid[2][3].

  1. We start by initializing our f array with 4 elements (since n = 4), and each element in f is set to 1, as there is only one way to reach each cell in the top row by moving to the right.

    Initial f array: [1, 1, 1, 1]

    This corresponds to the paths in the first row of the grid, where the robot can only move right.

  2. Then, we proceed to iterate over the rest of the rows in the grid (starting with the second row). For each cell we visit, we update its corresponding entry in f with the sum of the paths that can reach this cell from above and left.

    Since we are starting from the second row, f[j] contains the number of paths to the cell above [i - 1, j], and f[j - 1] contains the number of paths to the cell to the left [i, j - 1]. For the first cell in each row (the leftmost column), we don't need to update the value since there is still only one path to reach it by moving down from above.

  3. We iterate through the second row and update the array f:

    For j = 1: f[1] += f[0] (2 unique paths to grid[1][1]) For j = 2: f[2] += f[1] (3 unique paths to grid[1][2]) For j = 3: f[3] += f[2] (4 unique paths to grid[1][3])

    Updated f array after the second row: [1, 2, 3, 4]

  4. We repeat this process for the third row:

    For j = 1: f[1] += f[0] (3 unique paths to grid[2][1]) For j = 2: f[2] += f[1] (6 unique paths to grid[2][2]) For j = 3: f[3] += f[2] (10 unique paths to grid[2][3])

    Final f array after the third row: [1, 3, 6, 10]

  5. After processing all the rows, the value in the last cell of f, which is 10, represents the number of unique paths from the top-left corner to the bottom-right corner of the 3 x 4 grid.

  6. Consequently, f[-1] equals 10, so the function uniquePaths returns 10 as the final answer.

The solution can be visualized as filling up a table where each cell represents the number of paths leading to it. By the end of the procedure, the bottom-right cell contains the total count of unique paths the robot can take to reach the bottom-right corner of the grid.

Solution Implementation

1class Solution:
2    def uniquePaths(self, m: int, n: int) -> int:
3        # Initialize a list that will hold the number of unique paths to each cell
4        # in the first row. Initially, there's only one unique path to reach any cell
5        # in the first row since the only possible move is to the right.
6        path_counts = [1] * n
7      
8        # Iterate over the rows of the grid starting from the second row,
9        # since the first row has been initialized already.
10        for row in range(1, m):
11            # Iterate over the columns starting from the second column,
12            # since the first column only has one unique path (move down).
13            for col in range(1, n):
14                # The number of unique paths to reach this cell is the sum of
15                # the number of unique paths to reach the cell directly above
16                # and the number of unique paths to reach the cell to the left.
17                path_counts[col] += path_counts[col - 1]
18      
19        # Return the number of unique paths to reach the bottom-right corner of the grid,
20        # which is the last element in the path_counts list.
21        return path_counts[-1]
22
1class Solution {
2    public int uniquePaths(int m, int n) {
3        // Create an array to store the number of unique paths to each cell in the bottom row.
4        int[] pathCounts = new int[n];
5      
6        // Initialize the bottom row with 1s since there's only one way to reach each cell in the bottom row
7        // when only moving right.
8        Arrays.fill(pathCounts, 1);
9
10        // Loop over each cell starting from the second row up to the top row (since the bottom row is already filled).
11        for (int row = 1; row < m; ++row) {
12            // For each cell in a row, start from the second column since the first column of any row
13            // will only have one unique path (i.e., moving down from the cell above).
14            for (int col = 1; col < n; ++col) {
15                // The number of unique paths to the current cell is the sum of the unique paths to the cell
16                // directly above it and to the cell to the left of it.
17                pathCounts[col] += pathCounts[col - 1];
18            }
19        }
20      
21        // Return the number of unique paths to the top-right corner of the grid.
22        return pathCounts[n - 1];
23    }
24}
25
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6    // Function to calculate the unique paths in an m x n grid
7    int uniquePaths(int m, int n) {
8        // Create a vector with size 'n', initialize all elements to 1.
9        // The vector represents the number of ways to reach each cell in the grid.
10        vector<int> pathCounts(n, 1);
11
12        // Iterate over each row starting from the second one
13        for (int row = 1; row < m; ++row) {
14            // Iterate over each column starting from the second one
15            for (int col = 1; col < n; ++col) {
16                // Update the path count for the current cell
17                // The number of paths to the current cell is the sum of the paths
18                // from the cell directly above and the cell to the left.
19                pathCounts[col] += pathCounts[col - 1];
20            }
21        }
22
23        // Return the number of unique paths to the bottom-right cell
24        return pathCounts[n - 1];
25    }
26};
27
1function uniquePaths(rows: number, columns: number): number {
2  // Initialize an array 'dp' to store the number of unique paths to each cell in the first row
3  const dp: number[] = Array(columns).fill(1);
4
5  // Iterate over the grid starting from the second row, as the first row is preset to 1s
6  for (let row = 1; row < rows; ++row) {
7    // Iterate over each column starting from the second column
8    for (let col = 1; col < columns; ++col) {
9      // Update the dp array for the current cell based on the
10      // sum of the cell directly above and the cell to the left
11      dp[col] += dp[col - 1];
12    }
13  }
14  // Return the number of unique paths to the bottom-right cell
15  return dp[columns - 1];
16}
17
Not Sure What to Study? Take the 2-min Quiz๏ผš

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Time and Space Complexity

The time complexity of the provided solution is O(m * n), where m is the number of rows and n is the number of columns. This is because there are two nested loops: the outer loop runs m - 1 times (as the first row's values are all initialized to 1), and the inner loop runs n - 1 times for each iteration of the outer loop, resulting in a total of (m - 1) * (n - 1) iterations of the inner loop's body. However, since we're only interested in big O notation, this simplifies to O(m * n).

The space complexity of the solution is O(n), as it uses a single list f of size n to store intermediary results. This list is updated in-place, and no additional space that is dependent on m or n is used. As a result, the space complexity does not change with m, only with n.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which technique can we use to find the middle of a linked list?

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ