# Java graph solution 4ms using matrix

• The solution is to use a matrix to represent the graph. look for a path which can get the result
for example, given `[[a,b], [a,c]]` the way to get bc is b->a->c
and cache the traversed path if it's already calculated

``````public double[] calcEquation(String[][] equations, double[] values, String[][] queries) {
int index = 0;
Map<String, Integer> map = new HashMap();
// max size is values.lengt*2
// init the graph and fill in values
double[][] graph = new double[values.length * 2][values.length * 2];
for(int i = 0; i < equations.length; i++){
String[] ops = equations[i];
if(!map.containsKey(ops[0])){
map.put(ops[0],index);
index++;
}
if(!map.containsKey(ops[1])){
map.put(ops[1],index);
index++;
}
graph[map.get(ops[0])][map.get(ops[1])] = values[i];
graph[map.get(ops[1])][map.get(ops[0])] = 1/values[i];
}

double[] rt = new double[queries.length];
for(int i = 0 ; i < queries.length; i++){
String a = queries[i][0];
String b = queries[i][1];
Integer op1 = map.get(a);
Integer op2 = map.get(b);
// if operand doesn't exist
if(op1 == null || op2 == null) {
rt[i] = -1;
continue;
}
// if two operands are the same
if(op1 == op2) {
rt[i] = 1;
continue;
}
List<Double> path = new ArrayList();

findPath(graph, path, op1, op2, -1);
if(path.size() == 0){
rt[i] = -1;
continue;
}
double curR = 1;
for(Double r : path){
curR *= r;
}
rt[i] = curR;
}
return rt;
}

boolean findPath(double[][] graph, List<Double> path, int op1, int op2, int parent){
if(graph[op1][op2] != 0){
path.add(graph[op1][op2]);
return true;
}

for(int i =0; i < graph.length; i++){
if(graph[op1][i] != 0 && i != parent){
path.add(graph[op1][i]);
boolean found = findPath(graph, path, i, op2, op1);
if(found){
// memorize
double curR = 1;
for(Double r : path){
curR *= r;
}
graph[op1][op2] = curR;
return true;
}
path.remove(path.size() - 1);
}
}
return false;
}
``````

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