The trick here is to name the state correctly, then let the implementation follow. For 399. Evaluate Division, the solution in this repository is mainly a union-find solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: union-find, graph traversal.
The notes already sitting in the source point us in the right direction:
- union find
- WA
- [["a","c"],["b","e"],["c","d"],["e","d"]]
- [2.0,3.0,0.5,5.0]
Guide
When?
Reach for this shape when a direct simulation would work logically but waste time revisiting the same information. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are unite, calcEquation, oneGroup, dfs.
Guide
Why?
The point of the implementation is not to make the code longer. It is to avoid doing the same thinking twice.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- A set is doing the membership or uniqueness work, which keeps the main loop readable.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The two-dimensional vector is the memory of the solution: grid state, DP state, or adjacency shape.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01//union find
02//WA
03//[["a","c"],["b","e"],["c","d"],["e","d"]]
04//[2.0,3.0,0.5,5.0]
05//[["a","b"]]
06//in the "connect (a,b) and (b,c) to (a,c)" part, it fails when the path is too long
07class DSU{
08public:
09 map<string, string> parent;
10
11 DSU(set<string>& vertices){
12 for(string vertex : vertices){
13 parent[vertex] = vertex;
14 }
15 };
16
17 string find(string x){
18 if(parent[x] != x){
19 parent[x] = find(parent[x]);
20 }
21 return parent[x];
22 };
23
24 void unite(string x, string y){
25 parent[find(x)] = find(y);
26 };
27};
28
29class Solution {
30public:
31 vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
32 set<string> vertices;
33 map<vector<string>, double> edges;
34
35 for(int i = 0; i < equations.size(); i++){
36 vector<string> equation = equations[i];
37 double value = values[i];
38
39 vertices.insert(equation[0]);
40 vertices.insert(equation[1]);
41 edges[equation] = value;
42 edges[{equation[1], equation[0]}] = 1/value;
43 }
44
45 //check how many connected components there are?
46 DSU dsu(vertices);
47 for(auto it = edges.begin(); it != edges.end(); it++){
48 vector<string> edge = it->first;
49 dsu.unite(edge[0], edge[1]);
50 }
51
52 //key: root of that group
53 map<string, set<string>> groups;
54 for(string vertex : vertices){
55 groups[dsu.find(vertex)].insert(vertex);
56 }
57
58 // for(auto it = groups.begin(); it != groups.end(); ++it){
59 // cout << it->first << " : ";
60 // for(auto it2 = it->second.begin(); it2 != it->second.end(); ++it2){
61 // cout << *it2 << " ";
62 // }
63 // cout << endl;
64 // }
65
66 //for each connect component, full connect their nodes
67 //we have (a,b) and (b,c), now connect them to (a,c)
68 for(auto it = groups.begin(); it != groups.end(); it++){
69 vector<string> oneGroup(it->second.begin(), it->second.end());
70
71 for(int i = 0; i < oneGroup.size(); i++){
72 for(int j = i; j < oneGroup.size(); j++){
73 string vi = oneGroup[i], vj = oneGroup[j];
74 if(i == j){
75 edges[{vi, vj}] = 1.0;
76 }else if(edges.find({vi, vj}) != edges.end()){
77 //they are connected directly
78
79 }else{
80 // cout << vi << " and " << vj << " are connected indirectly" << endl;
81 //they can be connected indirectly
82 //find vertex vk s.t. {vi,vk} and {vk,vj} exist
83 for(int k = 0; k < oneGroup.size(); k++){
84 string vk = oneGroup[k];
85 if(edges.find({vi, vk}) != edges.end() && edges.find({vj, vk}) != edges.end()){
86 edges[{vi,vj}] = edges[{vi,vk}] * edges[{vk, vj}];
87 edges[{vj,vi}] = edges[{vj,vk}] * edges[{vk, vi}];
88 break;
89 }
90 }
91 }
92 }
93 }
94 }
95
96 // for(auto it = edges.begin(); it != edges.end(); ++it){
97 // cout << it->first[0] << ", " << it->first[1] << endl;
98 // }
99
100 vector<double> ans;
101
102 for(vector<string>& query: queries){
103 string numerator = query[0];
104 string denominator = query[1];
105 if(edges.find({numerator, denominator}) != edges.end()){
106 ans.push_back(edges[{numerator, denominator}]);
107 }else{
108 ans.push_back(-1.0);
109 }
110 }
111
112 return ans;
113 }
114};
115
116//Floyd Warshall
117//https://leetcode.com/problems/evaluate-division/discuss/88175/9-lines-%22Floydu2013Warshall%22-in-Python
118//Runtime: 8 ms, faster than 9.29% of C++ online submissions for Evaluate Division.
119//Memory Usage: 8.3 MB, less than 12.40% of C++ online submissions for Evaluate Division.
120class Solution {
121public:
122 vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
123 unordered_map<string, unordered_map<string, double>> quot;
124
125 int N = equations.size();
126
127 for(int i = 0; i < N; i++){
128 vector<string> equation = equations[i];
129 string num = equation[0], den = equation[1];
130 double value = values[i];
131 quot[num][num] = 1.0;
132 quot[den][den] = 1.0;
133 quot[num][den] = value;
134 quot[den][num] = 1.0/value;
135 }
136
137 for(auto it = quot.begin(); it != quot.end(); it++){
138 const string& k = it->first;
139 for(auto it2 = quot[k].begin(); it2 != quot[k].end(); it2++){
140 const string& i = it2->first;
141 for(auto it3 = quot[k].begin(); it3 != quot[k].end(); it3++){
142 const string& j = it3->first;
143 quot[i][j] = quot[i][k] * quot[k][j];
144 // adding this line gives WA!!!
145 //we don't need this line because i is not necessary <= j!
146 // quot[j][i] = quot[j][k] * quot[k][i];
147 }
148 }
149 }
150
151 vector<double> ans;
152
153 for(vector<string>& query : queries){
154 string num = query[0], den = query[1];
155
156 if(quot[num].find(den) == quot[num].end()){
157 ans.push_back(-1.0);
158 }else{
159 ans.push_back(quot[num][den]);
160 }
161 }
162
163 return ans;
164 }
165};
166
167//DFS
168//https://leetcode.com/problems/evaluate-division/discuss/171649/1ms-DFS-with-Explanations
169//Runtime: 0 ms, faster than 100.00% of C++ online submissions for Evaluate Division.
170//Memory Usage: 8.5 MB, less than 7.50% of C++ online submissions for Evaluate Division.
171class Solution {
172public:
173 double dfs(string start, string end, unordered_map<string, unordered_map<string, double>>& graph, unordered_set<string>& visited){
174 if(graph.find(start) == graph.end()){
175 return -1;
176 }
177
178 if(graph[start].find(end) != graph[start].end()){
179 return graph[start][end];
180 }
181
182 for(const auto& nei : graph[start]){
183 if(find(visited.begin(), visited.end(), nei.first) != visited.end())
184 continue;
185 visited.insert(nei.first);
186 double res;
187 if((res = dfs(nei.first, end, graph, visited)) != -1){
188 //optimization: runtime 4ms -> 0ms
189 return graph[start][end] = graph[start][nei.first] * res;
190 }
191 }
192
193 return -1;
194 }
195
196 vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
197 unordered_map<string, unordered_map<string, double>> quot;
198
199 int N = equations.size();
200
201 for(int i = 0; i < N; i++){
202 const vector<string>& equation = equations[i];
203 const string& num = equation[0], den = equation[1];
204 const double& value = values[i];
205 quot[num][num] = 1.0;
206 quot[den][den] = 1.0;
207 quot[num][den] = value;
208 quot[den][num] = 1.0/value;
209 }
210
211 vector<double> ans;
212 unordered_set<string> visited;
213
214 for(const vector<string>& query : queries){
215 const string& num = query[0], den = query[1];
216 visited = {num};
217 ans.push_back(dfs(num, den, quot, visited));
218 }
219
220 return ans;
221 }
222};
223
224//BFS
225//https://leetcode.com/problems/evaluate-division/discuss/88275/Python-fast-BFS-solution-with-detailed-explantion
226//Runtime: 4 ms, faster than 58.89% of C++ online submissions for Evaluate Division.
227//Memory Usage: 8.5 MB, less than 8.40% of C++ online submissions for Evaluate Division.
228class Solution {
229public:
230 double dfs(string start, string end, unordered_map<string, unordered_map<string, double>>& graph, unordered_set<string>& visited){
231 if(graph.find(start) == graph.end()){
232 return -1;
233 }
234
235 if(graph[start].find(end) != graph[start].end()){
236 return graph[start][end];
237 }
238
239 for(const auto& nei : graph[start]){
240 if(find(visited.begin(), visited.end(), nei.first) != visited.end())
241 continue;
242 visited.insert(nei.first);
243 double res;
244 if((res = dfs(nei.first, end, graph, visited)) != -1){
245 //optimization: runtime 4ms -> 0ms
246 return graph[start][end] = graph[start][nei.first] * res;
247 }
248 }
249
250 return -1;
251 }
252
253 vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
254 unordered_map<string, unordered_map<string, double>> quot;
255
256 int N = equations.size();
257
258 for(int i = 0; i < N; i++){
259 const vector<string>& equation = equations[i];
260 const string& num = equation[0], den = equation[1];
261 const double& value = values[i];
262 quot[num][num] = 1.0;
263 quot[den][den] = 1.0;
264 quot[num][den] = value;
265 quot[den][num] = 1.0/value;
266 }
267
268 vector<double> ans;
269 unordered_set<string> visited;
270
271 for(const vector<string>& query : queries){
272 const string& num = query[0], den = query[1];
273
274 double prod;
275
276 //cout << num << " - " << den << endl;
277
278 if(quot.find(num) == quot.end() || quot.find(den) == quot.end()){
279 //cout << "cannot find " << num << " or " << den << endl;
280 prod = -1.0;
281 }else if(quot[num].find(den) != quot[num].end()){
282 //cout << num << " - " << den << " already exist" << endl;
283 prod = quot[num][den];
284 }else{
285 //cout << "do BFS" << endl;
286 prod = -1.0;
287
288 //do BFS
289 //(node, current product)
290 queue<pair<string, double>> q;
291 q.push({num, 1.0});
292 visited = {num};
293
294 while(!q.empty()){
295 //cannot use pair<string, double>& here!!
296 pair<string, double> cur = q.front(); q.pop();
297
298 if(cur.first == den){
299 prod = cur.second;
300 break;
301 }
302
303 for(const pair<string, double>& nei : quot[cur.first]){
304 if(visited.find(nei.first) != visited.end())
305 continue;
306 visited.insert(nei.first);
307 /*
308 quot represents for the weight of edges,
309 not accumulative product,
310 so following line is wrong!
311 quot[cur.first][nei.first] = cur.second * nei.second;
312 */
313 q.push({nei.first, cur.second * nei.second});
314 }
315 }
316 }
317
318 //cout << prod << endl;
319 ans.push_back(prod);
320 }
321
322 return ans;
323 }
324};Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.