797. All Paths From Source to Target

Prompt

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

  • 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.

Approach

Examining the example same example above, each of the index of the given input represents the node. For instance, at index 0, [1, 2] represents that node 0 has a directed connection to its neighbors of node 1 and 2. Similarly, for index 1, this means that node 1 has a directed connection to node 3 and so on and so forth.

  1. Depth-First Search

Code

Python | Time: O(V + E) | Space: O(V) | V = the total # of vertices and E = the total # of edges

Thank you for reading!

In case if you haven’t yet joined my Discord server where I host daily sessions on data structures & algorithms for free, please join via the link shared below.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
John Kim

John Kim

75 Followers

iOS Developer | Full Stack Developer | Software Engineer | LinkedIn: john-kim-developer | GitHub: cloudiosx | Portfolio: cloudiosx.com