Detect Arbitrage

• Time : O(n^3)
• Space : O(n^2)

c++

#include <vector>
using namespace std;

bool detectArbitrage(vector<vector<double>> exchangeRates) {
	int n = exchangeRates.size();
	for(int k = 0; k < n; k++) {
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				exchangeRates[i][j] = max(exchangeRates[i][j], exchangeRates[i][k] * exchangeRates[k][j]);
			}
		}
	}
	for(int i = 0; i < n; i++)
		if(exchangeRates[i][i] > 1.0) return true;
  return false;
}

• Time : O(n^3)
• Space : O(n)

c++

int n;

bool bellmanFord(vector<vector<double>>& edges, vector<double>& weight) {
    bool update = false;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(weight[j] < weight[i] * edges[i][j]) {
                weight[j] = weight[i] * edges[i][j];
                update = true;
            }
        }
    }
    return update;
}


bool detectArbitrage(vector<vector<double>> exchangeRates) {
    n = exchangeRates.size();
    vector<double> weight(n, 1.0);
    for(int i = 0; i < n; i++)
        if(!bellmanFord(exchangeRates, weight))
            return false;
    return bellmanFord(exchangeRates, weight);
}