2 Perf-test cases failing

I have converted the binary tree into a bi-directional graph, then DFS on all nodes to find every path and append the path wherever sum equals to k.
2 perf test cases are failing for:
-perf-case 9

Hey by bi - directional graph , I think you intend to mean undirected graph.

Regarding your code implementation, I think its done inefficiently in a lot of places. Try to use your data structures efficiently and dont copy dictionaries . Statements like graph = edge_add(graph,u,i) are extremely inefficient since you are already changing the orignal graph by reference and then copying the entire dictionary. Also since you are storing all paths for a particular node , it could cause a memory issue and hence causing a Timeout (large memory consumption can often cause timeout errors in python).

Also for each node , you are storing all paths , and for each path you are calculating its sum in O(N) time . So the net time complexity should be O(N^3) in the worst case which is not optimal. Kindly not all these factors and re-implement your code .

Thank you so much for the explanation! I tried clearing out the inconsistencies, but it still fails. Is my approach incorrect? I am not able to figure this question for a long time and couldn’t understand the mentioned approach

The approach mentioned involves using hashing to solve the question. Also your approach isn’t incorrect. You need to optimize your DFS code accordingly to ensure that it is a O(N^2) code.

1 Like

Has this been resolved?

Closing this topic as your issue is resolved by the mentor. If it is still not resolved, Kindly un-mark the accepted solution or create a new topic and post this question as a reference link in the description of the new topic.