Count the paths

JavaView on GFG

Time: O(V+E)

Space: O(V)

Intuition

Count paths in a grid from top-left to bottom-right with obstacles. Standard DP.

Algorithm

1dp[i][j] = dp[i-1][j] + dp[i][j-1] if not obstacle, else 0.

Common Pitfalls

•Same as LC 62/63. Handle first row and column initialization. Obstacle sets dp to 0.

Count the paths.java

Java

// Approach: DFS/BFS from source to destination. Count all distinct simple paths.
// Time: O(V+E) Space: O(V)
import java.util.*;

class Solution {
    public int countPaths(int[][] edges, int V, int src, int dest) {
        int[] dp = new int[V];
        ArrayList<Integer>[] graph = new ArrayList[V];
        for (int i = 0; i < V; i++) {
            graph[i] = new ArrayList<>();
            dp[i] = -1;
        }

        for (int i = 0; i < edges.length; i++)
            graph[edges[i][0]].add(edges[i][1]);

        return dfs(graph, dp, src, dest);
    }

    int dfs(ArrayList<Integer>[] graph, int dp[], int src, int dest) {
        if (src == dest)
            return 1;
        if (dp[src] != -1)
            return dp[src];

        int count = 0;
        for (int i = 0; i < graph[src].size(); i++)
            count += dfs(graph, dp, graph[src].get(i), dest);

        return dp[src] = count;
    }
}

Was this solution helpful?