Is There a Bargain Loop That Pays You Forever
Solve this ProblemA network of trading posts has one-way trades, each with a cost (negative means you earn money). Decide whether the network contains a bargain loop: a cycle of trades that brings you back to the starting post with a negative total cost, so that repeating it earns money forever.
Bellman-Ford's relaxation rounds settle down after n − 1 rounds unless a negative cycle exists, which gives a simple test.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 7 trading posts numbered 0 … n-1; cost is an n × n matrix: cost[u][v] = 100 means no one-way trade from u to v, otherwise cost[u][v] (−9 … 9, zero allowed) is what you pay for the trade (negative means you gain money) - ◆
A trade from a post to itself is allowed (cost[u][u] may be a real value) - ◆
A bargain loop is a cycle of trades (returning to the starting post) whose total cost is negative; the loop may be anywhere in the network, not necessarily connected to a particular start - ◆
Return true if the network contains a bargain loop, otherwise false
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Search Every Cycle and Add Up Its Cost
BruteA bargain loop can always be chosen to visit each post only once, so search every cycle: from each starting post, follow the trades in a depth-first search that never visits a post twice, adding up the costs, and whenever a trade leads back to the starting post check whether the total cost is negative. This tries a huge number of cycles when the network is dense.
O(n · n!)O(n)1class Solution {
2 private boolean walk(int[][] cost, int start, int u, int total, boolean[] onPath) {
3 onPath[u] = true;
4 for (int v = 0; v < cost.length; v++) {
5 int c = cost[u][v];
6 if (c == 100) continue;
7 if (v == start) {
8 if (total + c < 0) return true;
9 } else if (!onPath[v] && walk(cost, start, v, total + c, onPath)) {
10 return true;
11 }
12 }
13 onPath[u] = false;
14 return false;
15 }
16
17 public boolean hasBargainLoop(int[][] cost) {
18 for (int start = 0; start < cost.length; start++) {
19 if (walk(cost, start, start, 0, new boolean[cost.length])) return true;
20 }
21 return false;
22 }
23}Optimal — Bellman-Ford Started From Every Post at Once
OptimalGive every post the starting value 0, as if a hidden post had a free trade to each of them; then negative loops anywhere in the network are reachable. Repeat rounds in which every trade (u, v) tries to lower dist[v] to dist[u] + cost. Without a negative loop the values stop changing after at most n − 1 rounds, so a round without any change means "no loop". If the values still change in every one of n rounds, a negative loop keeps lowering them forever.
O(n³) with a matrix (O(n · E) with lists)O(n)1class Solution {
2 public boolean hasBargainLoop(int[][] cost) {
3 int n = cost.length;
4 int[] dist = new int[n];
5 for (int round = 0; round < n; round++) {
6 boolean relaxed = false;
7 for (int u = 0; u < n; u++) {
8 for (int v = 0; v < n; v++) {
9 if (cost[u][v] != 100 && dist[u] + cost[u][v] < dist[v]) {
10 dist[v] = dist[u] + cost[u][v];
11 relaxed = true;
12 }
13 }
14 }
15 if (!relaxed) return false;
16 }
17 return true;
18 }
19}