Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
All Paths From Source to Target (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given a directed acyclic graph (DAG) with nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order.

The graph is given as follows: graph[i] is a list of all nodes you can visit from node i.

Examples

Example 1

  • Input: graph = [[2,3],[3,4],[3,4],[4],[]]
Image
  • Expected Output: [[0,2,3,4],[0,2,4],[0,3,4]]
  • Justification: You can go from node 0 to 4 via 2 and 3 or only 2 or only 3.

Example 2

  • Input: graph = [[1,3,4],[2,4],[3],[],[2,3]]
Image
  • Expected Output: [[0,1,4],[0,4]]
  • Justification: You can go from node 0 to 4 via 1 or directly.

Example 3

  • Input: graph = [[1,2,3],[2,3,4],[3,4],[],[3]]
  • Expected Output: [[0,1,2,4],[0,1,4],[0,2,4]]
  • Justification: There are total 3 paths from node 0 to 4.

Constraints:

  • n == graph.length
  • 2 <= n <= 15
  • 0 <= graph[i][j] < n
  • graph[i][j] != i (i.e., there will be no self-loops).
  • All the elements of graph[i] are unique.
  • The input graph is guaranteed to be a DAG.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible