Java 3ms Floyd-Warshall-like transitive closure


  • 0
    B

    The idea behind transitive closure is to pre-calculate the fully connected components (as much as we can - as there might be disconnected graph parts), so that we can get to constant time query evaluation. Getting to transitive closure in this case is just applying a modified Floyd-Warshall's all-pairs shortest path algorithm to calculate the first found two pairs connecting the third pair - we do not want minimization as ideally division is going to be deterministic. This is O(n^3) time and O(n^2) space.

    public class Solution {
        
        public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
            if (queries.length == 0) return new double[0];
        
            List<String> vars = new ArrayList<String>(); 
            
            for (int i = 0; i < equations.length; i++) {
                String a = equations[i][0];
                String b = equations[i][1];
                if (!vars.contains(a)) vars.add(a); 
                if (!vars.contains(b)) vars.add(b);
            }
            
            double[][] mx = new double[vars.size()][vars.size()];
            
            for (int i = 0; i < vars.size(); i++) {
                mx[i][i] = 1; 
            }
            
            for (int i = 0; i < equations.length; i++) {
                int a = vars.indexOf(equations[i][0]);
                int b = vars.indexOf(equations[i][1]);
                mx[a][b] = values[i];
                mx[b][a] = 1/values[i]; 
            }
            
            for (int i = 0; i < mx.length; i++) {
                for (int j = 0; j < mx.length; j++) {
                    if (mx[j][i] == 0) continue; 
                    for (int k = 0; k < mx.length; k++) {
                        if (mx[j][k] != 0) continue; 
                        if (mx[i][k] != 0) {
                            mx[j][k] = mx[i][k] * mx[j][i];
                            mx[k][j] = 1/mx[j][k];
                            continue;
                        }
                    }
                }
            }
            
            int q = 0;
            double[] result = new double[queries.length];    
            for (String[] query: queries) {
                int a = vars.indexOf(query[0]); 
                int b = vars.indexOf(query[1]);
                if (a == -1 || b == -1) {
                    result[q++] = -1; 
                    continue; 
                }
                
                result[q++] = mx[a][b] == 0 ? -1 : mx[a][b];
            }
            return result; 
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.