Currency Loop Profit
MediumAdvanced Graphs
Problem
An exchange desk trades n currencies. Each pairs[i] = [from, to] with rate rates[i] means 1 unit of from buys rates[i] units of to (only in that direction).
Return true if some sequence of trades starting and ending in the same currency multiplies the money by more than 1 (an arbitrage loop), and false otherwise.
Example 1
- Input:
- n = 3, pairs = [[0,1],[1,2],[2,0]], rates = [2.0,3.0,0.2]
- Output:
- true
1 unit of 0 → 2 units of 1 → 6 units of 2 → 1.2 units of 0.
Example 2
- Input:
- n = 3, pairs = [[0,1],[1,2],[2,0]], rates = [2.0,3.0,0.15]
- Output:
- false
The loop returns 0.9 units.
Example 3
- Input:
- n = 4, pairs = [[0,1],[1,0],[2,3],[3,2]], rates = [0.5,1.9,1.1,0.95]
- Output:
- true
2 → 3 → 2 multiplies by 1.045.
Constraints
- 1 ≤ n ≤ 200
- 0 ≤ pairs.length ≤ 2000
- 0 < rates[i] ≤ 100
- A loop counts only if its product exceeds 1 by more than 1e-9.
Hint
Show the first hint
Products are awkward for shortest-path algorithms. Which function turns products into sums?
Walkthrough
How to approach it
01Clarify before coding
- Are rates directional? Yes, each pair is one-way.
- Does a loop with product exactly 1 count? No, it must be strictly greater (beyond floating error).
- Must the loop involve a particular currency? No, any loop anywhere.
02Brute force
Enumerate every simple cycle and multiply its rates.
Cost: Exponential number of simple cycles.
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.