Welcome back, fellow coders! Today, we’re diving into one of my favorite types of LeetCode problems—Unique Paths. This problem is a great exercise in both recursion, with an emphasis on memoization to optimize the solution.
Problem Overview
The problem statement is simple but interesting: There is a robot on an m x n grid, starting at the top-left corner (0, 0). The robot can only move right or down, and it needs to reach the bottom-right corner (m – 1, n – 1). Our task is to find the number of unique paths the robot can take to reach the destination. You can read the problem in LeetCode website.
Constraints
- The grid size is determined by two integers,
mandn. - The answer should not exceed 2 * 10^9.
Approach Breakdown
1. Understanding the Grid and Movement
The robot can only move right or down, which simplifies the directions to be considered. This means at any point (i, j) on the grid, the robot can either move:
- Down to
(i + 1, j), or - Right to
(i, j + 1).
2. Recursion
A straightforward recursive approach would involve trying both possible moves (right and down) at each step until we reach the bottom-right corner. At this point, we increment the path count. If we move out of bounds, we return 0.
This solution, however, leads to a lot of redundant calculations. For example, different paths might lead the robot to the same grid cell multiple times, forcing us to recompute the number of ways from that point over and over.
3. Memoization
To optimize our solution, we can store the results of subproblems, which is where memoization comes into play. By storing the number of unique paths from each cell in a 2D memoization array, we avoid redundant calculations. If the robot visits the same cell through different paths, we simply retrieve the precomputed value.
Solution Code:
class Solution {
public int uniquePaths(int m, int n) {
int[][] memo = new int[m][n];
return move(m, n, 0, 0, memo);
}
static int move(int m, int n, int i, int j, int[][] memo) {
if (i >= m || j >= n) {
return 0; // Out of bounds
}
if (i == m - 1 && j == n - 1) {
return 1; // Reached bottom-right corner
}
if (memo[i][j] > 0) {
return memo[i][j]; // Already computed for this cell
}
// Compute number of paths from the current cell
memo[i][j] = move(m, n, i + 1, j, memo) + move(m, n, i, j + 1, memo);
return memo[i][j];
}
}
Step-by-Step Explanation
- Base Case: If the robot moves outside the grid, we return 0, indicating no valid path. If the robot reaches the bottom-right corner, we return 1, indicating one valid path.
- Memoization Check: Before computing the number of paths for a given cell, we check if we’ve already solved the subproblem. If so, we return the stored result.
- Recursive Calls: If no memoized result is available, we recursively explore the paths by moving down and right. The sum of these recursive calls gives the total number of paths from the current cell.
Time Complexity
With memoization, each cell is computed at most once, resulting in a time complexity of O(m * n). Without memoization, the time complexity would be exponentially larger, as we would re-explore many grid cells multiple times.
Conclusion
The beauty of this problem lies in its ability to illustrate the power of dynamic programming. By breaking the problem down into smaller subproblems and storing their results, we dramatically improve the efficiency of the solution. In fact, this solution performs optimally with a time complexity of O(m * n) and avoids the inefficiencies of a pure recursive approach.
If you enjoyed this article and found it helpful, don’t forget to subscribe and turn on notifications for more LeetCode solutions. Happy coding!
