Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

847. Shortest Path Visiting All Nodes

Time: $O(2^n \cdot n)$

Space: $O(2^n \cdot n)$

			


class Solution {
 public:
  int shortestPathLength(vector<vector<int>>& graph) {
    const int n = graph.size();
    const int goal = (1 << n) - 1;

    int ans = 0;
    queue<pair<int, int>> q;  // (u, state)
    vector<vector<bool>> seen(n, vector<bool>(1 << n));

    for (int i = 0; i < n; ++i)
      q.emplace(i, 1 << i);

    while (!q.empty()) {
      for (int sz = q.size(); sz > 0; --sz) {
        const auto [u, state] = q.front();
        q.pop();
        if (state == goal)
          return ans;
        if (seen[u][state])
          continue;
        seen[u][state] = true;
        for (const int v : graph[u])
          q.emplace(v, state | (1 << v));
      }
      ++ans;
    }

    return -1;
  }
};




			


class Solution {
  public int shortestPathLength(int[][] graph) {
    final int n = graph.length;
    final int goal = (1 << n) - 1;

    int ans = 0;
    Queue<Pair<Integer, Integer>> q = new ArrayDeque<>(); // (u, state)
    boolean[][] seen = new boolean[n][1 << n];

    for (int i = 0; i < n; ++i)
      q.offer(new Pair<>(i, 1 << i));

    while (!q.isEmpty()) {
      for (int sz = q.size(); sz > 0; --sz) {
        final int u = q.peek().getKey();
        final int state = q.poll().getValue();
        if (state == goal)
          return ans;
        if (seen[u][state])
          continue;
        seen[u][state] = true;
        for (final int v : graph[u])
          q.offer(new Pair<>(v, state | (1 << v)));
      }
      ++ans;
    }

    return -1;
  }
}




			


class Solution:
  def shortestPathLength(self, graph: List[List[int]]) -> int:
    n = len(graph)
    goal = (1 << n) - 1

    ans = 0
    q = deque()  # (u, state)
    seen = set()

    for i in range(n):
      q.append((i, 1 << i))

    while q:
      for _ in range(len(q)):
        u, state = q.popleft()
        if state == goal:
          return ans
        if (u, state) in seen:
          continue
        seen.add((u, state))
        for v in graph[u]:
          q.append((v, state | (1 << v)))
      ans += 1

    return -1