Eulerian Circuit Problems
3 Eulerian Circuit LeetCode problems · Browse tasks by difficulty and choose your next practice problem.
Learn the coding interview patterns behind these problems.
Build a route that uses each edge exactly once
An Eulerian route consumes edges, while allowing vertices to be visited repeatedly. This distinction matters for ticket itineraries and arrangements of directed pairs: two identical tickets are two separate edges. Hierholzer's algorithm follows unused edges and builds the final route when a vertex has no unused outgoing edges left.
When to use it
Use this approach when every edge must appear exactly once in a trail or circuit. A directed circuit needs equal in-degree and out-degree at each vertex and the appropriate connectivity among non-isolated vertices. An open trail instead has one start with an extra outgoing edge and one end with an extra incoming edge.
Worked example
Directed edges: A→B, B→A, A→C, C→A.
- Start a stack at A and consume edges to follow A→B→A→C→A.
- The last A has no unused outgoing edge. Pop it into the answer, then keep popping exhausted vertices.
- Reverse the popped sequence to recover the order of travel.
A→B→A→C→A uses all four edges once and returns to its start.
Time and space
With adjacency stacks and constant-time edge removal, construction takes O(V + E) time and O(V + E) storage including the route. Sorting adjacency lists for a lexical itinerary adds up to O(E log E) time.
Mistakes to check
- Degree checks alone do not establish connectivity. Verify that the route consumed every edge and contains E + 1 vertices.
- Keep parallel edges as separate entries; a set of neighboring vertices loses duplicate tickets.
- For lexical itineraries, choose the appropriate next edge during traversal but append vertices on backtracking. A greedy forward-only walk can get stuck early.
Further reading: Princeton Algorithms: directed Eulerian paths
Guide reviewed .