Problem statement

https://binarysearch.com/problems/Currency-Arbitrage/

Solution

Actually what is asked in this problem is to check if we have negative loop in graph on not. It can be done for example with Bellman-Ford algorithm.

Complexity

It is O(n^3) for time and O(n) for space.

Code

class Solution:
    def solve(self, M):
        n, INF = len(M), float("inf")
        dis = [INF] * n
        dis[0] = 0
    
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    dis[k] = min(dis[k], dis[j] - log(M[j][k]))

        for j in range(n):
            for k in range(n):
                if dis[j] != INF and dis[j] - log(M[j][k]) < dis[k]:
                    return True

        return False