Count maximum path in graph

Question

Given a directed graph represented as an adjacency list, write a function to count the maximum number of distinct paths from a starting node to a target node. The function should take the graph and the two nodes as input and return the total count of unique paths that can be traversed without revisiting any nodes.

Codemia · Accepted Answer

This problem involves counting distinct paths in a directed graph from a starting node to a target node without revisiting any nodes. The specific pattern that applies here is **Depth-First Search (DFS)** combined with **memoization**. DFS is suitable because it allows us to explore all possible paths recursively. Since multiple paths can lead to the same node, memoization will help avoid recalculating the number of paths from nodes we've already computed, thus optimizing our solution.

1. **Define the function**: Create a function `count_paths(graph, start, target)` that takes the graph and the two nodes as input.  
2. **Base Case**: If the start node is the same as the target node, return 1 since there is one valid path (the node itself).  
3. **Memoization**: Use a dictionary to store results of previously computed paths for nodes to avoid redundant calculations.  
4. **Recursive DFS**: For each neighbor of the current node, recursively call the function and sum the results.  
5. **Return the total count**: Return the memoized result for the current node once all neighbors have been processed.

**Example**: Given a graph represented as `{'A': ['B', 'C'], 'B': ['C'], 'C': []}` with `start = 'A'` and `target = 'C'`, the function will explore paths: `A -> B -> C` and `A -> C`, resulting in a total of 2 distinct paths.

```python
def count_paths(graph, start, target, memo=None):
    if memo is None:
        memo = {}
    
    # Base case: if start is the target, there's one path
    if start == target:
        return 1
    
    # Check if the result is already computed
    if start in memo:
        return memo[start]
    
    # Initialize path count
    path_count = 0
    
    # Explore each neighbor
    for neighbor in graph.get(start, []):
        path_count += count_paths(graph, neighbor, target, memo)
    
    # Memoize the result
    memo[start] = path_count
    return path_count
```

The time complexity of this solution is **O(V + E)**, where V is the number of vertices and E is the number of edges, because we traverse each node and edge at most once. The space complexity is also **O(V)** due to the memoization storing the results for each node, as well as the recursive call stack in the worst case. Given the constraints of the problem, this approach is efficient and optimal.

1. **No edges**: If the graph has no edges, the function should return 0 unless the start node is the same as the target node.  
2. **Self-loop**: If a node points to itself, it should be handled to avoid infinite recursion. In such cases, we can check if the current node is already visited during the DFS.  
3. **Disconnected components**: If the target node is not reachable from the start node, the function should return 0.  
4. **Start equals target**: If the start node is the same as the target node, directly return 1.  
5. **Large graphs**: Ensure that the algorithm handles large graphs efficiently with the memoization technique to prevent stack overflow or excessive computation.

Count maximum path in graph

Morgan Stanley

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Morgan Stanley Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string