Currency Arbitrage Detection

1. Define the problem

You are given a list of currencies and a rates matrix, where rates_i[j] is the amount of currency j you get for 1 unit of currency i (0 means no direct conversion). An arbitrage opportunity is a sequence of conversions that starts and ends on the same currency and leaves you with strictly more than you started with. Return true if any arbitrage opportunity exists, or false otherwise. Convert every rate to an edge weight of -log(rate) . Multiplying rates around a loop turning a profit becomes summing weights around that same loop to something below zero — exactly a negative-weight cycle , which Bellman-Ford already knows how to detect.

Constraints

1 ≤ currencies.length ≤ 12
rates.length == rates_i.length == currencies.length
0 ≤ rates_i[j]
rates_i[i] can be ignored

Example

Inputcurrencies = ['USD', 'EUR', 'GBP'], rates = [[1, 0.8, 0], [0, 1, 0.7], [1.9, 0, 1]]

Outputtrue

Explanation Converting USD → EUR → GBP → USD multiplies the rates 0.8 × 0.7 × 1.9 ≈ 1.064, turning 1 USD into about 1.064 USD.

2. Know the words first

In plain terms

Arbitrage: Converting currency A to B to C and back to A ending up with more of A than you started with, purely from the exchange rates lining up in your favor.
-log(rate): A trick for turning multiplication into addition: since log(a * b) = log(a) + log(b), a product of rates greater than 1 becomes a sum of -log(rate) values less than 0.

3. Visualize the solution

Turn rates into -log weights, then hunt for a negative cycle

USD0

EUR∞

GBP∞

Statusinit (src = USD)

dist[USD] = 0; dist[EUR] and dist[GBP] start at infinity. Edge weights are -log(rate): USD→EUR ≈ 0.223, EUR→GBP ≈ 0.357, GBP→USD ≈ -0.642.

What happens in this step

pass 1 of 2 begins (n - 1 = 2 regular passes, then 1 extra check), src = USD

dist[USD] = 0 (source)
dist[EUR] = dist[GBP] = ∞

edge weights: USD→EUR = -log(0.8) ≈ 0.223, EUR→GBP = -log(0.7) ≈ 0.357, GBP→USD = -log(1.9) ≈ -0.642

Each rate becomes -log(rate) so that multiplying rates around a loop turns into summing weights — a profitable loop (product > 1) becomes a negative-weight cycle Bellman-Ford can detect.

Step 1 of 4

Steps to visualize

Build a graph where each currency is a node and each known rate_i[j] > 0 becomes an edge weighted -log(rate_i[j]).
From every currency in turn, run Bellman-Ford: n - 1 relaxation passes, then one extra pass.
If the extra pass still finds an edge to relax from any starting currency, a negative-weight cycle exists.
A negative-weight cycle in the -log graph is exactly a profitable conversion loop in the original rates.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Turn rates into -log weights, then hunt for a negative cycle

USD0

EUR∞

GBP∞

Statusinit (src = USD)

dist[USD] = 0; dist[EUR] and dist[GBP] start at infinity. Edge weights are -log(rate): USD→EUR ≈ 0.223, EUR→GBP ≈ 0.357, GBP→USD ≈ -0.642.

What happens in this step

pass 1 of 2 begins (n - 1 = 2 regular passes, then 1 extra check), src = USD

dist[USD] = 0 (source)
dist[EUR] = dist[GBP] = ∞

edge weights: USD→EUR = -log(0.8) ≈ 0.223, EUR→GBP = -log(0.7) ≈ 0.357, GBP→USD = -log(1.9) ≈ -0.642

Each rate becomes -log(rate) so that multiplying rates around a loop turns into summing weights — a profitable loop (product > 1) becomes a negative-weight cycle Bellman-Ford can detect.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function hasArbitrageOpportunity(currencies, rates) {
  const n = currencies.length;
  const EPS = 1e-9;
  const edges = [];

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i !== j && rates[i][j] > 0) {
        edges.push([i, j, -Math.log(rates[i][j])]);
      }
    }
  }

  function hasNegativeCycleFrom(src) {
    const dist = new Array(n).fill(Infinity);
    dist[src] = 0;

    for (let i = 0; i < n - 1; i++) {
      for (const [u, v, w] of edges) {
        if (dist[u] !== Infinity && dist[u] + w < dist[v] - EPS) {
          dist[v] = dist[u] + w;
        }
      }
    }

    for (const [u, v, w] of edges) {
      if (dist[u] !== Infinity && dist[u] + w < dist[v] - EPS) {
        return true;
      }
    }

    return false;
  }

  for (let src = 0; src < n; src++) {
    if (hasNegativeCycleFrom(src)) {
      return true;
    }
  }

  return false;
}

Time: O(n^2 * e)
Space: O(n + e)

6. Test cases

Test cases

Input	Expected	Covers
`currencies = ['USD', 'EUR', 'GBP'], rates = [[1, 0.8, 0], [0, 1, 0.7], [1.9, 0, 1]]`	`true`	example from the docstring, a profitable 3-currency loop
`currencies = ['USD', 'EUR', 'GBP'], rates = [[1, 0.5, 0], [0, 1, 0.5], [0.5, 0, 1]]`	`false`	a loop exists but the product of rates is well under 1
`currencies = ['USD', 'EUR'], rates = [[1, 1.5], [0, 1]]`	`false`	only one direction of conversion exists, so no loop can form
`currencies = ['USD', 'EUR'], rates = [[1, 0.9], [1.2, 1]]`	`true`	the smallest possible arbitrage loop, back and forth between two currencies
`currencies = ['USD', 'EUR'], rates = [[1, 0.5], [2, 1]]`	`false`	a round trip that multiplies out to exactly 1, not a profit
`currencies = ['USD'], rates = [[1]]`	`false`	only one currency, no conversions are even possible
`currencies = ['USD', 'EUR', 'GBP', 'JPY'], rates = [[1, 0.9, 0, 0], [0, 1, 0.8, 0], [0, 0, 1, 130], [0.01, 0, 0, 1]]`	`false`	a longer 4-currency loop whose product still lands under 1
`currencies = ['USD', 'EUR'], rates = [[1, 2], [0.6, 1]]`	`true`	a clearly profitable round trip well above breakeven

Currency Arbitrage Detection