Java : Unique Paths

PROBLEM STATEMENT

A robot is located at the top-left corner of an m x n grid. The robot can only move either down or right at any point in time. The objective is to calculate the total number of unique paths the robot can take to reach the bottom-right corner of the grid.

INTUITION

This problem can be solved by recognizing its underlying structure, which is ideal for dynamic programming. The number of unique paths to any given cell (row, col) is the sum of the unique paths to the cell immediately above it (row-1, col) and the cell immediately to its left (row, col-1).

This is because to reach (row, col), the robot must have come from one of those two adjacent cells. By calculating the path counts for all cells systematically, starting from the top-left, the final answer for the bottom-right corner can be determined.

THE APPROACH

The approach is to use a 2D array, or a DP table, of size m x n to store the number of unique paths to each cell in the grid. The value at dp[i][j] will represent the total unique paths from the start (0, 0) to the cell (i, j).

The reason for this approach: It breaks the main problem into smaller, overlapping subproblems. The solution for each cell is built upon the pre-computed solutions of its neighbors, avoiding redundant calculations and ensuring an efficient solution.

ALGORITHM BREAKDOWN

Step 1: Initialize an m x n integer grid named path. This grid will store the path counts.

Step 2: Establish the base cases. The cells in the first row and first column have only one way to be reached.

• For the first column (col = 0), every cell can only be reached by moving down from the one above it. Set path[row][0] = 1 for all rows.

• For the first row (row = 0), every cell can only be reached by moving right from the one to its left. Set path[0][col] = 1 for all columns.

Step 3: Iterate through the rest of the grid, starting from cell (1, 1).

Step 4: For each cell (row, col), calculate the number of unique paths using the recurrence relation: path[row][col] = path[row-1][col] + path[row][col-1].

Step 5: After filling the entire grid, the value at the bottom-right corner, path[m-1][n-1], contains the total number of unique paths. Return this value.

The loops terminate once every cell in the m x n grid has been computed.

SOLUTION

Here is the complete implementation in Java:

public class Solution {
    /**
     * Calculates the number of unique paths in an m x n grid.
     * The robot can only move down or right.
     *
     * @param m The number of rows.
     * @param n The number of columns.
     * @return The total number of unique paths.
     */
    public int uniquePaths(int m, int n) {
        // Create a 2D array to store the number of paths to each cell.
        int[][] path = new int[m][n];

        // Base Case: Initialize the first column.
        // There is only one way to reach any cell in the first column (by moving down).
        for (int row = 0; row < m; row++) {
            path[row][0] = 1;
        }

        // Base Case: Initialize the first row.
        // There is only one way to reach any cell in the first row (by moving right).
        for (int col = 0; col < n; col++) {
            path[0][col] = 1;
        }

        // Fill the rest of the grid using the recurrence relation.
        for (int row = 1; row < m; row++) {
            for (int col = 1; col < n; col++) {
                // The number of paths to the current cell is the sum of paths
                // from the cell above and the cell to the left.
                path[row][col] = path[row - 1][col] + path[row][col - 1];
            }
        }

        // The final result is in the bottom-right corner of the grid.
        return path[m - 1][n - 1];
    }
}        

KEY IMPLEMENTATION POINTS

• DP Table: The int[][] path array serves as the memoization table to store intermediate results, which is the core of the dynamic programming solution.

• Base Cases: Correctly initializing the first row and first column to 1 is critical. These initial values act as the foundation for calculating paths for all other cells.

• Recurrence Relation: The logic path[row][col] = path[row-1][col] + path[row][col-1] correctly models the problem's constraints, as movement is restricted to down and right.

TIME AND SPACE COMPLEXITY

Time Complexity: O(m\*n)

• The algorithm iterates through each cell of the m x n grid exactly once to compute its value.

Space Complexity: O(m\*n)

• An auxiliary 2D array of size m x n is used to store the path counts for every cell.

EFFICIENCY NOTES This solution is efficient and optimal in terms of time. The space complexity can be further optimized to O(n) or O(min(m,n)). Since calculating the values for the current row only requires the values from the previous row, a full 2D grid is not necessary. One could use a 1D array to store the previous row's results while computing the current row.

💡 KEY TAKEAWAY Dynamic programming is a powerful technique for solving problems that can be decomposed into overlapping subproblems. By storing the results of smaller subproblems, redundant computations are avoided, leading to an efficient solution. This "bottom-up" approach of building the solution from base cases is a fundamental DP pattern.

#DSA #DynamicProgramming #Algorithms #Java #Coding #TechInterview #ProblemSolving