# java solution using 2D array, with explanation and example

• ``````public double[] calcEquation(String[][] equations, double[] values, String[][] query) {
ArrayList<String> map = new ArrayList<String>(); //mapping "variable name" -> "index"
double result[] = new double[query.length]; //result array
double[][] relation; //the 2D array that contains ratios of all pairs
/*I use a 2D array to represent the relation(ratio) between all input pairs
ex.   if a/b = 2.0, b/c = 3/0, then the 2D array(called "relation:) is:
a    b   c
a 1.0  2.0 6.0
b 0.5  1.0 3.0
c 1/6  1/3 1.0
our task is to fill out this array.
*/
//but an array is indexed by numbers, not strings. So we need a mapping: String->Integer, or "variable name" -> "its index in the 2D array" for the above example, a->0, b->1, c->2. This feature is implemented by the following for loop
int num=0;
for(int i=0;i<equations.length;i++){
if(!map.contains(equations[i][0])) {
num++;
}
if(!map.contains(equations[i][1])) {
num++;
}
}
relation = new double[num][num]; //create the 2D array with the number of variables
for(int i=0;i<equations.length;i++){ //fill out the ratio provided by the input
int ind1 = map.indexOf(equations[i][0]);
int ind2 = map.indexOf(equations[i][1]);
relation[ind1][ind2] = values[i];
}
for(int i=0;i<relation.length;i++){ //fill out 1.0's and the reciprocals, this loop can be combine with the above loop
for(int j=0;j<relation.length;j++){
if(i==j) relation[i][j] = 1;
if(relation[i][j]!=0) relation[j][i] = 1/relation[i][j];
}
}
/*until this point, the 2D array is:
a    b   c
a 1.0  2.0 0.0
b 0.5  1.0 3.0
c 0.0  1/3 1.0
We need <a,c> and <c,a> which are the ratio of a,c. The loops below fill out all missing elements
*/
boolean notQuit = true;
while(notQuit){
notQuit = false;
for(int i=0;i<relation.length;i++){
breakHere: //break point
for(int j=0;j<relation.length;j++){
if(relation[i][j]==0){ //0 element detect, trying to determine this ratio
for(int k=0;k<relation.length;k++){ //scan this column, from top to bottom
if(k!=i){
if(relation[k][j]!=0) { //find a variable that is already associated with the variable of this column
if(relation[i][k]!=0){ //find a variable that is associated with the variable found in the line above.
relation[i][j] = relation[i][k] * relation[k][j]; //calculate ratio and reciprocal
relation[j][i] = 1/relation[i][j];
notQuit=true; //if a zero element is changed into non-zero, always restart the outer for loop
break breakHere;
}
}
}
}
}
}
}
}
/* 2D array construction complete, current 2D array:
a    b   c
a 1.0  2.0 6.0
b 0.5  1.0 3.0
c 1/6  1/3 1.0
this 2D array is aready for any query. Note that if 2 variables are not associated, their element in the 2D is array remains 0.
*/
for(int i=0;i<query.length;i++){ //this loop fills out the result array
int ind1 = map.indexOf(query[i][0]);
int ind2 = map.indexOf(query[i][1]);
if(ind1<0 || ind2<0) result[i] = -1.0; //unknown variable
else if(relation[ind1][ind2]!=0)
result[i] = relation[ind1][ind2];
else
result[i] = -1.0; //not associated variables
}
return result;
}
``````

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