Grid Unique Paths

108.7k
0

Given positive integers m and n, consider a grid containing m rows and n columns. A robot begins at cell (0, 0) and must reach cell (m - 1, n - 1).

Only a right move or a down move is allowed from any cell. Return the number of distinct valid paths from the starting cell to the destination.

Example 1

Input: m = 3, n = 3
Output: 6
Explanation: To reach cell (2, 2), every valid path requires two Right (R) moves and two Down (D) moves. The 6 possible paths are: RRDD, RDRD, RDDR, DRRD, DRDR, and DDRR. Therefore, the total number of unique paths is 6.

Example 2

Input: m = 1, n = 4
Output: 1
Explanation: To reach cell (0, 3), the robot can only move Right (R) three times. The only valid path is RRR, so the total number of unique paths is 1.

Recursion

Every cell leaves at most two useful choices: move down or move right. Either choice creates a smaller version of the same counting problem, so recursion follows the grid naturally.

Let solve(row, column) represent the number of valid paths from cell (row, column) to the destination. A destination arrival contributes one path, while a boundary crossing contributes none. Counting starts at (0, 0) because every required path begins at the top-left cell.

Algorithm

  • Begin with a recursive state solve(row, column) so every call counts paths from one selected cell to the destination.

  • Return 1 at cell (m - 1, n - 1) because reaching the destination completes exactly one valid path.

  • Return 0 after crossing the bottom or right boundary because an outside position cannot reach the destination.

  • Explore solve(row + 1, column) so every path beginning with a down move is counted.

  • Explore solve(row, column + 1) so every path beginning with a right move is counted.

  • Add both results because down-first and right-first routes form separate path groups.

  • Start recursion from (0, 0) because the required journey begins at the top-left cell.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Counts paths from a cell to the destination.
int solve(int row, int column, int m, int n) {
// Reaching the target completes one valid route.
if (row == m - 1 && column == n - 1) {
return 1;
}
// Crossing a boundary cannot reach the target.
if (row >= m || column >= n) {
return 0;
}
// A down move advances to the next row.
int downPaths = solve(row + 1, column, m, n);
// A right move advances to the next column.
int rightPaths = solve(row, column + 1, m, n);
// Both move groups contain different routes.
return downPaths + rightPaths;
}
public:
// Returns the number of unique grid paths.
int uniquePaths(int m, int n) {
// Every valid path begins at the top-left cell.
return solve(0, 0, m, n);
}
};
// Driver code
int main() {
int m = 3;
int n = 3;
Solution obj;
cout << obj.uniquePaths(m, n) << endl;
return 0;
}

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Complexity Analysis

Time Complexity: O(2(M + N)), where M is the number of rows and N is the number of columns, because each non-terminal state can branch into two recursive calls across at most M + N - 2 moves.

Space Complexity: O(M + N), because the deepest recursion path can contain at most M + N - 1 active calls.

Memoization

Direct recursion reaches the same cell through many move orders. Every repeated arrival asks for the same remaining path count, so recalculation adds work without adding new information.

A two-dimensional array named dp stores the answer for every calculated (row, column) state. Recursion keeps the original choices and base cases, while a stored value returns immediately during later visits.

Algorithm

  • Begin with an m by n array named dp, filled with -1, so every untouched entry marks an uncalculated state.

  • Keep solve(row, column) as the path count from one cell to the destination so the recursive meaning remains unchanged.

  • Return 1 at the destination and 0 outside the grid because completed and invalid routes need no cache lookup.

  • Return dp[row][column] whenever a stored value exists because every later visit has the same remaining choices.

  • Explore the down and right states only for an uncached cell so each valid state performs useful work once.

  • Store the sum of both move groups in dp[row][column] because the cached value must represent every path from the selected cell.

  • Start the memoized recursion at (0, 0) because the cached answer for the starting state solves the complete problem.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Counts paths and stores calculated grid states.
int solve(
int row,
int column,
int m,
int n,
vector<vector<int>>& dp
) {
// Reaching the target completes one valid route.
if (row == m - 1 && column == n - 1) {
return 1;
}
// Crossing a boundary cannot reach the target.
if (row >= m || column >= n) {
return 0;
}
// A stored count removes repeated exploration.
if (dp[row][column] != -1) {
return dp[row][column];
}
// A down move advances to the next row.
int downPaths = solve(row + 1, column, m, n, dp);
// A right move advances to the next column.
int rightPaths = solve(row, column + 1, m, n, dp);
// Cache stores both disjoint move groups.
dp[row][column] = downPaths + rightPaths;
// Cached count represents the selected cell.
return dp[row][column];
}
public:
// Returns the number of unique grid paths.
int uniquePaths(int m, int n) {
// Minus one marks every uncalculated state.
vector<vector<int>> dp(m, vector<int>(n, -1));
// Counting begins from the required start.
return solve(0, 0, m, n, dp);
}
};
// Driver code
int main() {
int m = 3;
int n = 3;
Solution obj;
cout << obj.uniquePaths(m, n) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(M × N), where M is the number of rows and N is the number of columns, because each of the M × N grid states is computed once with constant work.

Space Complexity: O(M × N), because the dp table stores M × N values, while the recursion stack adds at most O(M + N) space.

Tabulation

Memoization still relies on recursive calls. Tabulation removes the call stack by calculating the same solve(row, column) states in an order keeping every required future state ready.

Each state needs the cell below and the cell to the right. Filling rows from bottom to top and columns from right to left makes both values available before the current state is calculated.

Algorithm

  • Begin with an m by n array named dp, filled with 0, so missing lower or right neighbors naturally contribute no paths.

  • Store dp[m - 1][n - 1] = 1 because the destination state represents one completed path.

  • Traverse rows from m - 1 down to 0 so every lower-row answer is ready before an upper row needs the answer.

  • Traverse columns from n - 1 down to 0 so every right-side answer in the current row is already available.

  • Preserve the destination value instead of recalculating the base state because the destination already represents a completed route.

  • Add the lower and right counts for every other cell because both next moves create distinct path groups.

  • Return dp[0][0] because the top-left state represents the required starting position.

Dry Run

Grid Unique Path Tabulation

Grid Unique Path Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Builds answers for every valid starting cell.
int uniquePaths(int m, int n) {
// Zero handles every missing neighboring cell.
vector<vector<int>> dp(m, vector<int>(n, 0));
// The destination contains one complete path.
dp[m - 1][n - 1] = 1;
// Reverse row order keeps lower states ready.
for (int row = m - 1; row >= 0; row--) {
// Reverse columns keep right states ready.
for (int column = n - 1; column >= 0; column--) {
// Preserve the known destination base value.
if (row == m - 1 && column == n - 1) {
continue;
}
// A missing lower cell contributes no path.
int downPaths = row + 1 < m
? dp[row + 1][column]
: 0;
// A missing right cell contributes no path.
int rightPaths = column + 1 < n
? dp[row][column + 1]
: 0;
// Both valid next moves form distinct paths.
dp[row][column] = downPaths + rightPaths;
}
}
// The top-left state represents the full grid.
return dp[0][0];
}
};
// Driver code
int main() {
int m = 3;
int n = 3;
Solution obj;
cout << obj.uniquePaths(m, n) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(M × N), where M is the number of rows and N is the number of columns, because every grid cell is processed once with constant work.

Space Complexity: O(M × N), because the dp table stores one path count for every grid cell, while the iterative approach uses no recursion stack.

Space Optimization

Tabulation reveals a smaller storage need. A cell uses only the value directly below from the completed next row and the value directly right from the current row.

Arrays nextRow and currentRow preserve exactly the required values. Each current count adds the lower and right answers, and the completed currentRow becomes nextRow only after every column has been processed.

Algorithm

  • Begin with nextRow filled with 0 so positions below the bottom boundary contribute no paths.

  • Traverse rows from bottom to top because nextRow must hold the completed row directly below the current row.

  • Create a fresh zero-filled currentRow for each row so right-side values can be built without overwriting lower-row answers.

  • Traverse columns from right to left because currentRow[column + 1] must be ready before calculating the current cell.

  • Store 1 at the destination state because reaching the bottom-right cell completes one valid path.

  • Calculate current by adding nextRow[column] and the available right-side value because both moves form distinct route groups.

  • Shift currentRow into nextRow after the whole row is complete so no lower-row value is replaced early, then return nextRow[0] after the top row becomes the retained row.

Dry Run

Grid Unique Path Space Optimization

Grid Unique Path Space Optimization

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Counts paths with two retained grid rows.
int uniquePaths(int m, int n) {
// Zero represents positions below the grid.
vector<int> nextRow(n, 0);
// Reverse row order keeps lower values ready.
for (int row = m - 1; row >= 0; row--) {
// A fresh row protects lower-row values.
vector<int> currentRow(n, 0);
// Reverse columns keep right values ready.
for (int column = n - 1; column >= 0; column--) {
// The destination completes one route.
if (row == m - 1 && column == n - 1) {
currentRow[column] = 1;
continue;
}
// The retained lower row supplies down paths.
int downPaths = nextRow[column];
// A missing right cell contributes no path.
int rightPaths = column + 1 < n
? currentRow[column + 1]
: 0;
// Current combines the two distinct moves.
int current = downPaths + rightPaths;
// Store the count for the current grid cell.
currentRow[column] = current;
}
// Shift only after the complete row is ready.
nextRow = currentRow;
}
// The retained top row contains the full answer.
return nextRow[0];
}
};
// Driver code
int main() {
int m = 3;
int n = 3;
Solution obj;
cout << obj.uniquePaths(m, n) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(M × N), where M is the number of rows and N is the number of columns, because every grid cell is processed once with constant work.

Space Complexity: O(N), because nextRow and currentRow each store N values, while all older rows are discarded.

Interview follow-up Questions

Yes. Only one movement direction remains available, so a single straight sequence reaches the destination.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Largest Divisible Subset

Given an array nums containing distinct positive integers, return a maximum-length subset. For every pair of values first and second in the subset, either first % second == 0 or second % first == 0...

73.5k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

An array prices stores a stock price for each day, and an integer fee gives the cost of one completed transaction. Any number of transactions may be completed, but only one share may...

65.7k
Dynamic Programming

Check If a Subset with the Target Sum Exists

Input: arr = [1, 2, 3, 4] , target = 4 Output: true Explanation: Subset [4] reaches the target. Subset [1, 3] also reaches the target. Input: arr = [2, 4, 6] , target = 5 Output: false Explanation:...

55.1k
Comments0