62. Unique Paths

Unique Paths (LeetCode 62) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Unique Paths on Grid) subpattern.

• Blind 75 · #59 of 75 · 2-D Dynamic Programming
• NeetCode 150 · #111 of 150 · 2-D Dynamic Programming
• NeetCode 250 · #191 of 250 · 2-D Dynamic Programming

How to solve Unique Paths

Unique Paths is a Unique Paths on Grid problem, part of Dynamic Programming (DP) Patterns. Count paths and find optimal paths in grids using 2D dynamic programming.

Work towards the solution in these steps:

1. Consider using dynamic programming to solve this problem efficiently, as it involves counting the number of ways to reach a point on a grid.
2. Think about how the number of unique paths to a particular cell depends on the paths to the cells immediately above and to the left of it.
3. Try to define a 2D DP array where each element represents the number of unique paths to that cell.

The reference solution runs in O(m * n) time and O(n) space.

The Unique Paths solution and editorial walks through the full approach with reference code.

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.

The test cases are generated so that the answer will be less than or equal to 2 109.

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

Topics and companies

Topics: Math, Dynamic Programming, Combinatorics.

Reported in interviews at Amazon, Bloomberg, ByteDance, Facebook, Goldman Sachs, Google, Microsoft, Qualtrics, Salesforce, VMware.

How to practise Unique Paths on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(n) space.

Open Unique Paths in the code editor, or read the Unique Paths editorial for a worked solution with its approach and complexity analysis.

Where Unique Paths sits in the DSA pattern sheet

• Dynamic Programming (DP) Patterns pattern guide
• 2D Array (Unique Paths on Grid) subpattern
• The full DSA patterns sheet

Problems related to Unique Paths

Other problems that use the same 2D Array (Unique Paths on Grid) and Dynamic Programming (DP) Patterns techniques:

• Count Square Submatrices with All Ones — Medium, same subpattern
• Interleaving String — Medium, same subpattern
• Longest Increasing Path in a Matrix — Hard, same subpattern
• Maximal Square — Medium, same subpattern
• Minimum Falling Path Sum — Medium, same subpattern
• Minimum Path Sum — Medium, same subpattern

Unique Paths FAQ