class Solution { public boolean equationsPossible(String[] equations) { /* Q39 graph playlist , DSU concept 1) union all letters with == 2) process equations with != , if any 2 variable have same parent return false */ int n = equations.length; parent = new int[26]; //total letters 26 size = new int[26]; for(int i = 0 ;i < 26 ; i++){ parent[i] = i; size[i] = 1; } //unioning all equations variables with '==' for(String eq : equations){ int a = (eq.charAt(0) - 'a') ; int b = (eq.charAt(3) - 'a') ; char symbol = eq.charAt(1); if(symbol == '=') union(a,b); } //processing equations with != for(String eq : equations){ int a = (eq.charAt(0) - 'a') ; int b = (eq.charAt(3) - 'a') ; char symbol = eq.charAt(1); if(symbol == '!'){ int p1 = findparent(a) , p2 = findparent(b); if(p1 == p2) return false; } } return true; } int parent[]; int size[]; public int findparent(int u){ if(parent[u] == u) return u; return parent[u] = findparent(parent[u]); } public boolean union(int x , int y){ int lx = findparent(x); int ly = findparent(y); if(lx != ly){ if(size[lx] > size[ly]){ parent[ly] = lx; } else{ parent[lx] = ly; if(size[lx] == size[ly]) size[ly] ++; } return false; } //if parents same return true; return true; } }