mafeshsho8lmafeshsho8l
Get Started
All coding questions

Unique Paths

medium
NeetCode 150dynamic-programmingmathmatrix

Problem

A robot starts at the top-left of an m by n grid and may move only right or down. Count the number of distinct paths it can take to reach the bottom-right corner.

Examples

Input: m = 3, n = 7
Output: 28
There are 28 distinct right/down paths.
Input: m = 3, n = 2
Output: 3
Three ways to reach the corner.

Constraints

  • • 1 <= m, n <= 100
  • • The answer fits in a 32-bit integer
Hints(tap to reveal)
  • 1. Paths to a cell sum the paths from above and from the left.
  • 2. A single row of state suffices.
Optimal approach(spoiler)
  1. Each cell's path count is the sum of the cell above and the cell to the left.
  2. Initialize the first row and first column to one.
  3. Fill the grid row by row, reusing a one-dimensional rolling array.
  4. Return the value at the bottom-right.
  5. O(m * n) time, O(n) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor