Clone Graph — Editorial

Opening the reading…

Intuitionthe representation already contains the whole graph

The input does not give you node objects connected by pointers. It gives one adjacency list per node: row i describes the neighbors of node i + 1. Cloning this graph therefore means producing new outer and inner lists while preserving every integer in every row. No traversal is needed to discover structure that is already written in the input.

Create one empty output row for each input row, then copy the neighbor values from row i into output row i. The values identify nodes, so copying a value preserves an edge; creating fresh vectors ensures the result does not reuse the input's list storage. The empty input is the only case with no rows to copy.

Approach

Return an empty adjacency list immediately when adjList is empty, because there are no nodes and attempting to use its size as though a node existed would create the wrong result.

Store the number of nodes as n and allocate clone with n empty rows, because every input row needs a distinct output row even when that row has no neighbors.

Visit each input row i from 0 through n - 1, because row i and output row i both describe node i + 1; changing the row position would change which node owns the edges.

Visit every neighbor value v in adjList[i] and append v to clone[i], because each listed value represents one edge that must appear in the corresponding cloned row.

Return clone after all rows are copied, because returning before the loops finish would produce a partial graph and no later traversal is needed to complete it.

Complexitycounting adjacency entries, not only nodes

MEASURE	BOUND	WHY
Time	O(n + m)	Allocating n output rows accounts for the n term, and the inner loop processes each of the m stored neighbor entries exactly once. No entry is revisited, so the total work does not multiply across rows; in the densest allowed shape, m can be O(n^2).
Space	O(1) extra	The output adjacency list occupies O(n + m) space, but required output storage is excluded. Apart from that output, the algorithm keeps only the node count and loop variables, so the extra bound remains O(1) even when the input is dense.

Here n is the number of nodes and m is the total number of neighbor entries across all rows. For an undirected graph, each edge normally contributes two entries, but m is the quantity the loops actually process.

Annotated solutionC++ · direct adjacency-list copy · the representation does the traversal's work

CPPAllocate fresh rows and copy every neighbor entry into its matching row.

#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> cloneGraph(vector<vector<int>>& adjList) {
        if (adjList.empty()) return {};

        int n = adjList.size();
        vector<vector<int>> clone(n);

        for (int i = 0; i < n; ++i) {
            for (int v : adjList[i]) {
                clone[i].push_back(v);
            }
        }

        return clone;
    }
};

The index relationship is the key line of reasoning: input row i describes node i + 1, and clone[i] must describe that same node in the copy. The code copies values rather than trying to manufacture a separate mapping because node values already identify the endpoints in this representation. The newly allocated vectors provide the deep copy's independent storage.