FastPrep
Problem · Graph

Shortest Path Visiting All Nodes

Learn this problem
● HardInMobi logoInMobiFULLTIMEONSITE INTERVIEW

Problem statement

You are given a connected, undirected graph with n nodes labeled from 0 to n - 1. The adjacency list graph[i] contains every node joined to node i by an edge.

Return the minimum number of edges in a walk that visits every node at least once. You may start and finish at any node, revisit nodes, and traverse an edge more than once.

Function

shortestPathLength(graph: int[][]) → int

Examples

Example 1

graph = [[1,2,3],[0],[0],[0]]return = 4

One shortest walk is 1 - 0 - 2 - 0 - 3, which uses four edges.

Example 2

graph = [[1],[0,2,4],[1,3,4],[2],[1,2]]return = 4

A four-edge walk such as 0 - 1 - 4 - 2 - 3 visits all five nodes.

Constraints

  • 1 <= n <= 12
  • graph.length == n
  • 0 <= graph[i].length < n
  • graph[i] does not contain i or duplicate neighbors.
  • If j appears in graph[i], then i appears in graph[j].
  • The graph is connected.

More InMobi problems

drafts saved locally
public int shortestPathLength(int[][] graph) {
    // write your code here
}
graph[[1,2,3],[0],[0],[0]]
expected4
checking account