In this article, we will learn to resolve the Unique Paths with Obstacles problem in Java by using a dynamic programming algorithm

Problem

  • Given a 2D array A[M][N], aka Grid / Maze / Matrix

  • Write an algorithm to count the number of unique paths to reach A[M-1][N-1] from A[0][0]

  • At any cell (x, y), you can either go to (x+1, y) or (x, y+1) if there's no obstacle

Example

  • Input A[3][3] with values {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}}, 0 and 1 represent for empty and obstacle respectively

  • Expected output 2

Approach: Dynamic programming bottom-up

  • Fill up matrix cache[i][j] to count unique paths to (i,j)

  • cache[i][j] = cache[i-1][j] + cache[i][j-1] for each (i,j) with A[i][j] as 0

  • cache[0][0] = 1, cache[i][0] and cache[0][j] are base cases

  • cache[rows-1][cols-1] is final result

public class DP_UniquePaths_Obstacles {  
    int countUniquePaths(int[][] A) {
        if (A[0][0] == 1) return 0;

        int rows = A.length;
        int cols = A[0].length;
        int[][] cache = new int[rows][cols];

        cache[0][0] = 1;

        for (int i = 1; i < rows; i++) {
            if (A[i][0] == 0)
                cache[i][0] = cache[i-1][0];
        }

        for (int j = 1; j < cols; j++) {
            if (A[0][j] == 0)
                cache[0][j] = cache[0][j-1];
        }

        for (int i = 1; i < rows; i++) {
            for (int j = 1; j < cols; j++) {
                if (A[i][j] == 0)
                    cache[i][j] = cache[i-1][j] + cache[i][j-1];
            }
        }

        return cache[rows-1][cols-1];
    }

    public static void main(String[] args) {
        DP_UniquePaths_Obstacles uniquePaths = new DP_UniquePaths_Obstacles();
        int[][] A = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
        System.out.println(uniquePaths.countUniquePaths(A));
    }
}
  • Output
2
  • Time complexity is O(mn) and space complexity is O(mn), where m is the number of rows, and n is the number of columns
AlgorithmDynamic Programming