All Paths From Source to Target

MediumGraphsbacktracking

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are given a **directed acyclic graph** with n nodes labeled 0 to n - 1, where graph[i] lists the nodes reachable from i by a single edge. Return every path that starts at node 0 and ends at node n - 1. Each path is a list of node labels in visiting order. The paths may be returned in any order, but each path's nodes must be listed from 0 to n - 1. If no path exists, return an empty list.

Examples

Input: graph = [[1,2,3],[2],[3],[]]
Output: [[0,1,2,3],[0,2,3],[0,3]]
Three distinct routes lead from node 0 to node 3.
Input: graph = [[1],[]]
Output: [[0,1]]
The single edge 0 -> 1 is the only path.

Constraints

  • n == graph.length
  • 2 <= n <= 15
  • 0 <= graph[i][j] < n and graph[i][j] != i
  • graph[i] has no duplicates
  • The graph is acyclic

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More backtracking problems