Given two integers m and n, representing the number of rows and columns in a grid, return the number of unique paths from the top-left cell to the bottom-right cell.
Only right and down moves are allowed.
Example 1
Input: m = 3, n = 7
Output: 28
Explanation: To reach the bottom-right cell, the robot needs 2 down moves and 6 right moves.
There are 28 different ways to arrange these moves.
Example 2
Input: m = 3, n = 2
Output: 3
Explanation: The possible paths are:
Right -> Down -> DownDown -> Right -> DownDown -> Down -> Right
So the answer is 3.
Approach
Every valid path from the top-left to the bottom-right has fixed moves. To move from row 0 to row m - 1, the robot must move down exactly m - 1 times. To move from column 0 to column n - 1, the robot must move right exactly n - 1 times.
So total moves are: (m - 1) + (n - 1) = m + n - 2
Now the problem becomes: Out of m + n - 2 positions, choose where to place the down moves or right moves.
So the answer is: C(m + n - 2, m - 1) or C(m + n - 2, n - 1)
Both give the same result.
Algorithm
Calculate the total number of moves as
m + n - 2. This is fixed because every path must make the same number of down and right moves.Choose the smaller value between
m - 1andn - 1. This keeps the combination calculation shorter becauseC(total, r) = C(total, total - r).Start the answer as
1because combination multiplication builds the result step by step.Multiply by the next numerator value and divide by the current denominator value in each step. This avoids calculating huge factorials directly.
Return the final answer after all selected positions have been counted.
Dry Run
Count Paths Using Combinatorics Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: /* Calculates nCr without using factorials, so large intermediate values are avoided. */ long long calculateCombination(int totalMoves, int chosenMoves) { // Stores the combination result built step by step. long long result = 1; for (int i = 1; i <= chosenMoves; i++) { /* Multiply first and then divide to keep the result accurate at every step. */ result = result * (totalMoves - chosenMoves + i) / i; } return result; }public: /* Counts unique grid paths using combinatorics. */ int uniquePaths(int m, int n) { /* If there is only one row or one column, the robot has only one straight path. */ if (m == 1 || n == 1) { return 1; } // Total moves are fixed for every valid path. int totalMoves = m + n - 2; /* Choose the smaller move count to reduce the number of multiplication steps. */ int chosenMoves = min(m - 1, n - 1); return (int)calculateCombination(totalMoves, chosenMoves); }};int main() { // Driver code starts int m = 3; int n = 7; Solution obj; cout << obj.uniquePaths(m, n) << endl; return 0;}Complexity Analysis
Time Complexity: O(min(m, n)) because only the smaller number of moves is used in the combination calculation.
Space Complexity: O(1) because constant space is used.
Interview follow-up Questions
Every valid path has the same number of right and down moves. The only thing that changes is their order, so the answer can be counted using combinations.
Be the first to add a comment.