Detect Arbitrage

Tags

Detect Arbitrage

Category

Graphs

Difficulty

Hard

Problem Statement

Given a table of currency exchange rates (an n x n matrix where rates[i][j] is the rate to convert currency i to currency j), determine if there exists a sequence of conversions that starts and ends with the same currency and yields a profit (i.e., an arbitrage opportunity).

Intuition

An arbitrage exists when a cycle of conversions multiplies to more than 1. Multiplying rates along a path is equivalent to adding their logarithms. Taking the negative logarithm of each rate transforms the problem into detecting a negative-weight cycle in a graph — which is exactly what the Bellman-Ford algorithm does.

Approach

  1. Build a directed graph with n nodes (currencies). The edge weight from i to j is -log(rates[i][j]).
  2. Run the Bellman-Ford algorithm from any source node:
    • Initialize dist[source] = 0, all others to infinity.
    • Relax all edges n - 1 times.
    • On the n-th iteration, if any edge can still be relaxed, a negative cycle exists — arbitrage is possible.
  3. Since the graph is complete (every currency converts to every other), a single Bellman-Ford run from any source suffices. However, to be safe with disconnected components, you can initialize all distances to 0.

Pseudocode

function detectArbitrage(rates):
    n = length(rates)

    // Transform rates to negative log weights
    edges = []
    for i from 0 to n-1:
        for j from 0 to n-1:
            if i != j:
                edges.append((i, j, -log(rates[i][j])))

    // Bellman-Ford: initialize all distances to 0
    dist = array of size n, filled with 0

    // Relax edges n-1 times
    for iteration from 1 to n-1:
        for (u, v, w) in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w

    // Check for negative cycle (n-th relaxation)
    for (u, v, w) in edges:
        if dist[u] + w < dist[v]:
            return true    // arbitrage detected

    return false

Time & Space Complexity

MeasureComplexityJustification
TimeO(n^3)Bellman-Ford: n-1 iterations over n^2 edges
SpaceO(n^2)Edge list storage (or use the matrix directly)

Key Insights

  • The negative log transform is the key mathematical insight: product > 1 becomes sum of -log(values) < 0, i.e., a negative cycle.
  • Initializing all distances to 0 (instead of infinity for all but the source) ensures we detect negative cycles reachable from any starting currency, not just a single source.
  • Bellman-Ford is preferred over Dijkstra here because weights can be negative after the log transform.
  • An alternative approach: use Floyd-Warshall to compute all-pairs shortest paths and check if any diagonal entry dist[i][i] < 0.

Edge Cases

  • Single currency: no conversion possible; no arbitrage.
  • Two currencies: arbitrage exists if rates[0][1] * rates[1][0] > 1.
  • Identity rates (all 1.0): no arbitrage; -log(1) = 0, no negative cycles.
  • Floating-point precision: use an epsilon tolerance when checking for relaxation to avoid false positives from rounding errors.
  • Rate of 0: log(0) is undefined; this represents an impossible conversion and should be handled as no edge.

Linked mentions