Log inSign up
mediumLeetCodeNot Started

Unique Paths

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]).

The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

### Example 1 - Input: m = 3, n = 7 - Output: 28

### Example 2 - Input: m = 3, n = 2 - Output: 3 - Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Down -> Down 2. Down -> Down -> Right 3. Down -> Right -> Down

Constraints:

  • 1 <= m, n <= 100
  • The answer will be less than or equal to 2 * 109

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Model 2D grid path counting via dynamic programming.
  • Space-optimize from O(m * n) to O(n) 1D array.
  • Understand the direct combinatorial formulation C(m+n-2, m-1).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Robot navigating m x n grid.
  • Moves strictly right and down.
  • Counting all unique paths.

Algorithmic Decision Tree:

  • dp[j] initialized to 1 for all j (only 1 way to traverse row 0).
  • Roll downwards m - 1 times.

Connected Patterns:

Unique Paths IIMinimum Path SumNumber of Ways to Stay in the Same Place

1. Recursive Exploration

Intuition

Recursively branch into moving down and right until reaching (m - 1, n - 1).

Algorithm

  1. Define solve(r, c).
  2. If r == m - 1 && c == n - 1, return 1.
  3. If r >= m || c >= n, return 0.
  4. Return solve(r + 1, c) + solve(r, c + 1).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class Solution {
6 int solve(int r, int c, int m, int n) {
7 if (r == m - 1 && c == n - 1) return 1;
8 if (r >= m || c >= n) return 0;
9 return solve(r + 1, c, m, n) + solve(r, c + 1, m, n);
10 }
11public:
12 int uniquePaths(int m, int n) {
13 return solve(0, 0, m, n);
14 }
15};
16
17int main() {
18 Solution sol;
19 cout << "Unique Paths: " << sol.uniquePaths(3, 7) << endl;
20 return 0;
21}

Time & Space Complexity

  • Time complexity: O(2^(m + n))
  • Space complexity: O(m + n) call stack

2. 1D Rolling Row DP (O(m * n) Time, O(n) Space)

Intuition

Maintain a 1D array of size n initialized to 1. For each subsequent row, update dp[j] += dp[j-1].

Algorithm

  1. Initialize dp array of size n with 1.
  2. Loop i from 1 to m - 1:
  3. For j from 1 to n - 1:
  4. dp[j] += dp[j - 1].
  5. Return dp[n - 1].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class Solution {
7public:
8 int uniquePaths(int m, int n) {
9 vector<int> dp(n, 1);
10
11 for (int i = 1; i < m; ++i) {
12 for (int j = 1; j < n; ++j) {
13 dp[j] += dp[j - 1];
14 }
15 }
16
17 return dp[n - 1];
18 }
19};
20
21int main() {
22 Solution sol;
23 cout << "Unique Paths: " << sol.uniquePaths(3, 7) << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(n)

3. Combinatorics (O(min(m, n)) Time, O(1) Space)

Intuition

Compute C(m + n - 2, min(m - 1, n - 1)) iteratively using 64-bit integer multiplication to avoid factorial overflow.

Algorithm

  1. Let N = m + n - 2 and r = min(m - 1, n - 1).
  2. Initialize ans = 1 (64-bit integer).
  3. For i = 1 to r:
  4. ans = ans * (N - r + i) / i.
  5. Return ans.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <algorithm>
3
4using namespace std;
5
6class Solution {
7public:
8 int uniquePaths(int m, int n) {
9 int N = m + n - 2;
10 int r = min(m - 1, n - 1);
11 long long ans = 1;
12
13 for (int i = 1; i <= r; ++i) {
14 ans = ans * (N - r + i) / i;
15 }
16
17 return (int)ans;
18 }
19};
20
21int main() {
22 Solution sol;
23 cout << "Unique Paths: " << sol.uniquePaths(3, 7) << endl;
24 return 0;
25}

Time & Space Complexity

  • Time complexity: O(min(m, n))
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive DFSO(2^(m + n))O(m + n)Exhaustive branching over down and right.Subproblem overlap
2.1D Rolling Row DPO(m * n)O(n)Maintain one row of path counts updated in-place.None
3.Combinatorics C(N, r)OptimalO(min(m, n))O(1)Mathematical combination of choices.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Computing N! directly in combinatorics: factorials overflow standard integer types even for small m, n ~ 25.

Pitfall 2:

Initializing DP table with 0s instead of 1s.

Crucial Edge Cases to Validate:

  • m = 1 or n = 1: Single row or column; only 1 unique path straight along the line.
  • m = 2, n = 2: 2 paths (right-down or down-right).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. State both the DP formulation and the mathematical combinatorial formula C(m+n-2, m-1) to show comprehensive knowledge.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the total number of moves always equal to (m - 1) + (n - 1) = m + n - 2?

Back to DSA Sheet