Endless Discount Loop
EasyAdvanced Graphs
Problem
A marketplace has n listings. Each swaps[i] = [u, v, c] lets a trader exchange listing u for listing v paying c (a negative c means the trader receives money).
Return true if there is a sequence of swaps that starts and ends at the same listing with a negative total cost (an endless money loop), wherever it is in the network; otherwise return false.
Example 1
- Input:
- n = 3, swaps = [[0,1,2],[1,2,-3],[2,0,0]]
- Output:
- true
0 → 1 → 2 → 0 costs 2 - 3 + 0 = -1.
Example 2
- Input:
- n = 3, swaps = [[0,1,2],[1,2,-3],[2,0,1]]
- Output:
- false
The only loop totals exactly 0.
Example 3
- Input:
- n = 4, swaps = [[0,1,1],[2,3,-2],[3,2,1]]
- Output:
- true
The loop 2 → 3 → 2 totals -1, even though listing 0 cannot reach it.
Constraints
- 1 ≤ n ≤ 1000
- 0 ≤ swaps.length ≤ 5000
- -10^4 ≤ c ≤ 10^4
- u = v is allowed.
Hint
Show the first hint
Bellman-Ford converges in n - 1 rounds unless a negative cycle keeps lowering some distance.
Walkthrough
How to approach it
01Clarify before coding
- Does the loop have to pass through a specific listing? No, any loop anywhere counts.
- Does a loop with total 0 count? No, it must be strictly negative.
- Can a listing swap with itself? Yes; a negative self-swap is a loop on its own.
02Brute force
Enumerate every simple cycle (e.g. Johnson's algorithm) and sum its costs.
Cost: The number of simple cycles can be exponential.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.