Find if there is a path of more than k length from a source

The problem, simply

You get a map: stops joined by two-way roads, and each road has a length. You also get a starting stop and a number k.

Is there a walk that starts at the starting stop, never visits the same stop twice, and has a total length more than k? Answer yes or no. You do not have to end anywhere special.

A story to remember it

Picture it

Examples

Way 1: the simple way

Find the longest walk from the start, then compare it with k.

1. Mark the current stop as used.
2. For each road to a stop that is not used, find the longest walk from that stop, and add the road length.
3. Keep the biggest. Unmark the stop on the way out, so other walks may use it.
4. At the end, answer longest > k.

import java.util.*;

class Solution {
    // graph.get(u) holds roads as {v, length}
    public boolean pathMoreThanK(List<List<int[]>> graph, int source, int k) {
        boolean[] used = new boolean[graph.size()];
        return longest(graph, source, used) > k;
    }

    // the longest walk that starts at u and never repeats a stop
    private int longest(List<List<int[]>> graph, int u, boolean[] used) {
        used[u] = true;
        int best = 0;
        for (int[] road : graph.get(u)) {
            int v = road[0], len = road[1];
            if (!used[v]) best = Math.max(best, len + longest(graph, v, used));
        }
        used[u] = false;             // free the stop for other walks
        return best;
    }
}

How long it takes: in a map where every stop touches every other, the number of walks without repeats is about (V - 1)!, so this is O(V!). Extra room: the used marks and the call stack, O(V).

Way 2: the clever way

We do not need the longest walk. We only need one walk that is long enough. So carry the length as you walk, and stop the whole search the first moment it goes past k.

1. Start at the source with length 0, and mark it used.
2. If the length is more than k, answer yes right away.
3. Otherwise try each road to an unused stop: mark it, walk, and if that walk said yes, say yes too.
4. If the walk said no, unmark the stop and try the next road. This undo is the backtracking.
5. If no road works, say no.

import java.util.*;

class Solution {
    public boolean pathMoreThanK(List<List<int[]>> graph, int source, int k) {
        boolean[] used = new boolean[graph.size()];
        used[source] = true;
        return walk(graph, source, 0, k, used);
    }

    private boolean walk(List<List<int[]>> graph, int u, int total, int k, boolean[] used) {
        if (total > k) return true;              // long enough, stop everything
        for (int[] road : graph.get(u)) {
            int v = road[0], len = road[1];
            if (used[v]) continue;               // never visit a stop twice
            used[v] = true;
            if (walk(graph, v, total + len, k, used)) return true;
            used[v] = false;                     // step back and free the stop
        }
        return false;
    }

    // helper: build the two-way map from {a, b, length} triples
    static List<List<int[]>> build(int n, int[][] roads) {
        List<List<int[]>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] r : roads) {
            g.get(r[0]).add(new int[]{r[1], r[2]});
            g.get(r[1]).add(new int[]{r[0], r[2]});
        }
        return g;
    }
}

How long it takes: still O(V!) in the worst case, for example when the answer is no and every walk must be tried. When the answer is yes, it often stops very early. Extra room: O(V) for the marks and the call stack.

There is no fast trick here. Finding the longest walk without repeats is one of the famous hard problems (it is NP-hard), so nobody knows a way that is always quick.

Watch out for

• Using >= instead of >. The question says more than k.
• Forgetting to mark the source. A walk could come back to it, which is a repeat.
• Returning from the loop without unmarking when the answer is no. The marks must be clean for the next road.
• In the yes case you may return without unmarking. That is fine because the search is over.

What interviewers ask next

• Why not use Dijkstra with negative lengths to find the longest walk? Flipping the signs makes negative loops, and shortest path methods break on those. The problem is NP-hard, so no such shortcut exists.
• What if the map has one-way roads and no loops (a DAG)? Then walks can never repeat a stop. Go through the stops in topological order and keep the longest length to each stop, in O(V + E).
• What if V is at most about 20? Use a bitmask table: best[mask][v] is the longest walk that used exactly the stops in mask and ends at v. That is O(2^V * V^2), much better than V!.
• Print the walk too. Keep a list, add a stop when you mark it and remove it when you unmark it. When the answer is yes, the list holds the walk.

Remember this

Grown-up words: stops are vertices, roads are weighted edges, a walk with no repeats is a simple path, the used marks are a visited array that is reset on the way back, which is backtracking, and the tree of walks is the recursion tree of a depth first search.