I'm struggling to calculate the runtime of this backtracking algorithm on LC. Any ideas how to get started? I wish I can post a syntax highlighted post on blind, so please don't mind the screenshot. TC: 150k, yoe 10 Bananas eaten: ♾️
Draw the recursion tree 🌲
Good luck on your Coinbase interview. The complexity of that algo is O(V + E). Time and space once you flatten that JSON into a graph and do a dfs
Thank you. You can tell just from looking at it? Are you an LC god?
Yes. I have achieved God status by failing countless interviews.
Typically backtracking is o(n!) Or o(2^n). This one feels exponential but how can I know for sure. I can run the code with some counter but I may not come up with the worst case.