3
$\begingroup$

I just solved the following Leetcode problem: All Paths From Source to Target

Here is my solution:

class Solution {
public:
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
        vector<int> curr = { 0 };
        backtrack(graph, curr, 0);
        return answer;
    }
private:
    vector<vector<int>> answer;
    void backtrack(vector<vector<int>>& graph, vector<int>& curr, int node) {
        if (node == graph.size() - 1) {
            answer.push_back(curr);
            return;
        }

        for (int neighbor : graph[node]) {
            curr.push_back(neighbor);
            backtrack(graph, curr, neighbor);
            curr.pop_back();
        }
    }
};

I was told that the time complexity of the algorithm is $O(n \cdot 2 ^ n)$, because there are at most $2^n$ different paths in the graph, and for each path, we do $O(n)$ work to copy the path to the answer array.

However, this only represents the leaf nodes part of the recursion tree, how about the work done in non-leaf nodes of the recursion tree? I understand that the work done at every non-leaf node is $O(1)$ but how do I know how many there are?

Improve this question
$\endgroup$
1
  • $\begingroup$ "this only represents the leaf nodes part of the recursion tree, how about the work done in leaf nodes of the recursion tree?" I do not see what distinction you're trying to make here. $\endgroup$ Commented 16 hours ago

2 Answers 2

Reset to default
2
$\begingroup$

You wrote leaf nodes twice, I assume you ask about internal nodes?

Each recursive call corresponds to a distinct prefix of some source-to-target path, so the total number of (non-leaf) calls is at most $n\cdot 2^n$, hence the $O(1)$ work at internal nodes is also $O(n2^n)$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you for your answer but sorry I'm not sure I understand fully. Could you please detail the proof? And also, how do we prove that this statement is true? "Each recursive call corresponds to a distinct prefix of some source-to-target path". To be honeste I'm no sure I fully understand the statement, sorry I lack some knowledge about DSA. $\endgroup$ Commented 9 hours ago
1
$\begingroup$

You can look at it this way: At the end of the path, you copy the vector of nodes and that takes $O(n)$ time, because there are (at most) $n$ nodes.

But each of the nodes was put there by a previous recursive call at the inner node ie. this part:

curr.push_back(neighbor);
backtrack(graph, curr, neighbor);
curr.pop_back();

Each of these lines is $O(1)$ (amortized, but that's good enough), so to add $n$ nodes, they took $O(n)$ time and their complexity can be added to the work at the leaf and doesn't raise it.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.