Unique Paths - Practice Coding Problems

Unique Paths - Problem

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 * 10^9.

Input & Output

Example 1 — Small Grid

$ Input: m = 3, n = 7

› Output: 28

💡 Note: Robot needs 2 down moves and 6 right moves. Total arrangements: C(8,2) = 8!/(2!×6!) = 28 unique paths.

Example 2 — Square Grid

$ Input: m = 3, n = 3

› Output: 6

💡 Note: Robot needs 2 down and 2 right moves. Arrangements: C(4,2) = 6. Paths: RRDD, RDRD, RDDR, DRRD, DRDR, DDRR.

Example 3 — Single Row

$ Input: m = 1, n = 5

› Output: 1

💡 Note: Only one path possible: move right 4 times (RRRR) since we're already in the correct row.

Constraints

1 ≤ m, n ≤ 100
The answer will be less than or equal to 2 × 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Grid dimensions m=3, n=3

Process

Robot can only move right or down

Output

Count all possible unique paths

Key Takeaway

🎯 Key Insight: This is a combinatorics problem - we're arranging a fixed number of moves in different orders

Asked in

G Google 45 a Amazon 38 M Microsoft 32 f Facebook 28

The key insight is recognizing this as a combinatorics problem: we need exactly (m-1) down moves and (n-1) right moves, and we're choosing positions for these moves. The optimal approach uses the mathematical formula C(m+n-2, m-1) for O(min(m,n)) time and O(1) space. Dynamic programming approaches work well too with O(m×n) time/space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Memoization (Top-Down DP)	O(m×n)	O(m×n)	Cache recursive results to avoid recomputation
Mathematical Formula (Combinatorics)	O(min(m,n))	O(1)	Use combination formula to calculate paths directly
2D Dynamic Programming	O(m×n)	O(m×n)	Build solution bottom-up using 2D table
Recursive Brute Force	O(2^(m+n))	O(m+n)	Try all possible paths recursively

Memoization (Top-Down DP) — Algorithm Steps

Create memo table to store computed results
Use same recursive logic as brute force
Before computing, check if result already exists in memo
Store result in memo before returning

Visualization

Tap to expand

Step-by-Step Walkthrough

Compute

Calculate path count for each cell once

Store

Cache result in memo table

Reuse

Return cached value for repeated subproblems

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

#define MAX_SIZE 101
int memo[MAX_SIZE][MAX_SIZE];
int m_global, n_global;

int countPaths(int row, int col) {
    // Base case: reached destination
    if (row == m_global - 1 && col == n_global - 1) {
        return 1;
    }
    // Out of bounds
    if (row >= m_global || col >= n_global) {
        return 0;
    }
    
    // Check memo
    if (memo[row][col] != -1) {
        return memo[row][col];
    }
    
    // Compute and store in memo
    int right = countPaths(row, col + 1);
    int down = countPaths(row + 1, col);
    memo[row][col] = right + down;
    
    return memo[row][col];
}

int solution(int m, int n) {
    m_global = m;
    n_global = n;
    memset(memo, -1, sizeof(memo));
    return countPaths(0, 0);
}

int main() {
    int m, n;
    scanf("%d", &m);
    scanf("%d", &n);
    printf("%d\n", solution(m, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Each cell is computed only once and stored in memo

✓ Linear Growth

Space Complexity

O(m×n)

Memo table stores results for all m×n cells plus recursion stack

⚡ Linearithmic Space

587.0K Views

High Frequency

~15 min Avg. Time

8.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoization (Top-Down DP) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler