LeetCode 2097 - Valid Arrangement of Pairs

This problem gives us a list of directed pairs, where each pair [starti, endi] represents a directed edge from starti to endi. We must rearrange all pairs so that adjacent pairs connect correctly.

leetcodehardarraydepth-first-searchgraph-theoryeulerian-circuit

LeetCode Problem 2097

Difficulty: 🔴 Hard
Topics: Array, Depth-First Search, Graph Theory, Eulerian Circuit

Solution

LeetCode 2097 - Valid Arrangement of Pairs

Problem Understanding

This problem gives us a list of directed pairs, where each pair [starti, endi] represents a directed edge from starti to endi. We must rearrange all pairs so that adjacent pairs connect correctly.

More specifically, if the arrangement is:

[a, b], [c, d], [e, f]

then it must satisfy:

b == c
d == e

In other words, the end of one pair must equal the start of the next pair.

The important detail is that every pair must be used exactly once. We are not allowed to skip edges or reuse them.

The problem guarantees that at least one valid arrangement exists. That guarantee is extremely important because it means the graph formed by these directed edges always has an Eulerian path.

We can reinterpret the problem as a graph problem:

  • Each unique number is a node.
  • Each pair [u, v] is a directed edge from u to v.
  • We need to find an ordering of edges such that consecutive edges connect properly.
  • Since every edge must be used exactly once, this becomes an Eulerian path problem in a directed graph.

The constraints are large:

  • Up to 10^5 pairs
  • Node values up to 10^9

These constraints immediately rule out brute-force permutation approaches. A factorial-time solution would be impossible. We need a linear or near-linear graph algorithm.

There are several edge cases worth noticing immediately:

  • The graph may contain cycles.
  • Multiple edges can connect through the same node.
  • The valid arrangement may start at a node whose outdegree is exactly one greater than its indegree.
  • In Eulerian circuit cases, every node may have equal indegree and outdegree.
  • Node values are large, so arrays indexed by node value are not practical. We need hash maps.

The guarantee that a valid arrangement exists means we do not need to handle impossible cases.

Approaches

Brute Force Approach

A brute-force solution would try every possible ordering of the pairs and check whether consecutive pairs connect correctly.

For n pairs, there are n! possible permutations. For each permutation, we would verify whether:

pairs[i - 1][1] == pairs[i][0]

for every adjacent pair.

This approach is correct because it eventually checks every possible arrangement and therefore must find a valid one if it exists.

However, the complexity is catastrophic. Even for n = 15, factorial growth becomes infeasible. Since the constraint allows up to 10^5 pairs, brute force is completely impossible.

Optimal Approach

The key observation is that this is exactly the definition of an Eulerian path in a directed graph.

An Eulerian path is a path that uses every edge exactly once.

Each pair is an edge:

[start, end]

and the required chaining condition:

previous_end == next_start

is exactly how edges connect in a graph traversal.

This means we can solve the problem using Hierholzer's Algorithm, which constructs an Eulerian path in linear time.

The algorithm works by:

  1. Building an adjacency list.
  2. Tracking indegree and outdegree.
  3. Finding the correct starting node.
  4. Performing DFS while consuming edges.
  5. Reversing the traversal result.

Because each edge is visited exactly once, the solution runs in O(n) time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n!) O(n) Tries all permutations
Optimal O(n) O(n) Uses Hierholzer's Algorithm for Eulerian path

Algorithm Walkthrough

Step 1: Build the Graph

We create an adjacency list where:

graph[u] = list of destination nodes

Each pair [u, v] becomes a directed edge from u to v.

At the same time, we track:

  • outdegree[u] += 1
  • indegree[v] += 1

We use hash maps because node values can be as large as 10^9.

Step 2: Find the Starting Node

For a directed Eulerian path:

  • One node may have:
outdegree = indegree + 1

This node must be the start.

  • One node may have:
indegree = outdegree + 1

This node must be the end.

  • All other nodes must have equal indegree and outdegree.

If no node has extra outdegree, then the graph forms an Eulerian circuit, and we can start anywhere with outgoing edges.

Step 3: Perform Hierholzer's DFS

We perform DFS from the starting node.

While the current node still has outgoing edges:

  1. Remove one edge from the adjacency list.
  2. Recursively DFS into the neighbor.

Once a node has no remaining outgoing edges, we append it to the path.

This produces the Eulerian traversal in reverse order.

Step 4: Reverse the Path

The DFS records nodes in reverse Eulerian order because nodes are added only after exhausting all outgoing edges.

So we reverse the collected path.

Step 5: Convert Nodes into Edges

Suppose the final node order is:

[a, b, c, d]

Then the edge arrangement becomes:

[a, b]
[b, c]
[c, d]

This reconstructs the required pair ordering.

Why it works

Hierholzer's Algorithm guarantees that every edge is used exactly once. Since edges are only appended to the final path after all outgoing edges are exhausted, the traversal naturally stitches cycles together into one valid Eulerian path.

Because the problem guarantees a valid arrangement exists, the graph always satisfies Eulerian path conditions. Therefore, the algorithm always produces a valid ordering of all pairs.

Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
        graph = defaultdict(list)
        indegree = defaultdict(int)
        outdegree = defaultdict(int)

        # Build graph and degree counts
        for start, end in pairs:
            graph[start].append(end)
            outdegree[start] += 1
            indegree[end] += 1

        # Find starting node
        start_node = pairs[0][0]

        for node in outdegree:
            if outdegree[node] == indegree[node] + 1:
                start_node = node
                break

        path = []

        # Hierholzer DFS
        def dfs(node: int) -> None:
            while graph[node]:
                next_node = graph[node].pop()
                dfs(next_node)

            path.append(node)

        dfs(start_node)

        path.reverse()

        # Convert node path into edge path
        result = []

        for i in range(len(path) - 1):
            result.append([path[i], path[i + 1]])

        return result

The implementation begins by constructing the adjacency list and degree counters. Each pair contributes one outgoing edge from start and one incoming edge into end.

Next, we determine the Eulerian path starting node. If a node has one extra outgoing edge, it must be the starting point. Otherwise, we can safely start from the first pair's start value because the graph forms a circuit.

The DFS function implements Hierholzer's Algorithm. Each edge is removed from the adjacency list exactly once using pop(). Once a node has no remaining outgoing edges, it is added to the path.

After DFS finishes, the node order is reversed because nodes were recorded during backtracking.

Finally, we rebuild the edge sequence by converting adjacent node pairs into directed edges.

Go Solution

package main

func validArrangement(pairs [][]int) [][]int {
	graph := make(map[int][]int)
	indegree := make(map[int]int)
	outdegree := make(map[int]int)

	// Build graph
	for _, pair := range pairs {
		start := pair[0]
		end := pair[1]

		graph[start] = append(graph[start], end)
		outdegree[start]++
		indegree[end]++
	}

	// Find starting node
	startNode := pairs[0][0]

	for node := range outdegree {
		if outdegree[node] == indegree[node]+1 {
			startNode = node
			break
		}
	}

	path := []int{}

	var dfs func(int)

	dfs = func(node int) {
		for len(graph[node]) > 0 {
			lastIndex := len(graph[node]) - 1
			nextNode := graph[node][lastIndex]

			graph[node] = graph[node][:lastIndex]

			dfs(nextNode)
		}

		path = append(path, node)
	}

	dfs(startNode)

	// Reverse path
	for left, right := 0, len(path)-1; left < right; left, right = left+1, right-1 {
		path[left], path[right] = path[right], path[left]
	}

	// Build result edges
	result := [][]int{}

	for i := 0; i < len(path)-1; i++ {
		result = append(result, []int{path[i], path[i+1]})
	}

	return result
}

The Go solution follows the same logic as the Python version. Maps are used instead of dictionaries for adjacency lists and degree tracking.

Slices naturally support stack-like behavior, so we remove edges using slice truncation from the end of each adjacency list.

Go does not require special overflow handling here because all node values fit safely inside standard integers.

Worked Examples

Example 1

pairs = [[5,1],[4,5],[11,9],[9,4]]

Graph Construction

Edge Graph State
[5,1] 5 -> [1]
[4,5] 4 -> [5]
[11,9] 11 -> [9]
[9,4] 9 -> [4]

Degree Counts

Node Outdegree Indegree
5 1 1
1 0 1
4 1 1
11 1 0
9 1 1

Node 11 has:

outdegree = indegree + 1

So traversal starts at 11.

DFS Traversal

Traversal sequence:

11 -> 9 -> 4 -> 5 -> 1

Path collected during backtracking:

[1, 5, 4, 9, 11]

After reversing:

[11, 9, 4, 5, 1]

Convert into edges:

[[11,9],[9,4],[4,5],[5,1]]

Example 2

pairs = [[1,3],[3,2],[2,1]]

This forms a cycle.

Degree Counts

Node Outdegree Indegree
1 1 1
3 1 1
2 1 1

No special start node exists, so we start from 1.

DFS path:

1 -> 3 -> 2 -> 1

Edge arrangement:

[[1,3],[3,2],[2,1]]

Example 3

pairs = [[1,2],[1,3],[2,1]]

Degree Counts

Node Outdegree Indegree
1 2 1
2 1 1
3 0 1

Node 1 is the start.

DFS traversal eventually produces:

[1, 2, 1, 3]

Result:

[[1,2],[2,1],[1,3]]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each edge is visited exactly once
Space O(n) Graph storage and recursion stack

The adjacency list stores every edge exactly once, so graph construction is linear. Hierholzer's Algorithm removes and processes each edge exactly one time, giving linear traversal complexity.

The recursion stack can grow to O(n) in the worst case for a long chain graph.

Test Cases

from collections import Counter

def is_valid(arrangement):
    for i in range(1, len(arrangement)):
        if arrangement[i - 1][1] != arrangement[i][0]:
            return False
    return True

sol = Solution()

# Example 1
pairs = [[5,1],[4,5],[11,9],[9,4]]
result = sol.validArrangement(pairs)
assert is_valid(result)  # basic chain validation
assert Counter(map(tuple, result)) == Counter(map(tuple, pairs))  # uses all edges

# Example 2
pairs = [[1,3],[3,2],[2,1]]
result = sol.validArrangement(pairs)
assert is_valid(result)  # cycle graph
assert Counter(map(tuple, result)) == Counter(map(tuple, pairs))

# Example 3
pairs = [[1,2],[1,3],[2,1]]
result = sol.validArrangement(pairs)
assert is_valid(result)  # branching graph
assert Counter(map(tuple, result)) == Counter(map(tuple, pairs))

# Single edge
pairs = [[10,20]]
result = sol.validArrangement(pairs)
assert result == [[10,20]]  # minimum input size

# Long chain
pairs = [[1,2],[2,3],[3,4],[4,5]]
result = sol.validArrangement(pairs)
assert is_valid(result)  # simple path
assert Counter(map(tuple, result)) == Counter(map(tuple, pairs))

# Eulerian circuit
pairs = [[1,2],[2,3],[3,1]]
result = sol.validArrangement(pairs)
assert is_valid(result)  # closed cycle
assert Counter(map(tuple, result)) == Counter(map(tuple, pairs))

# Multiple cycles connected
pairs = [[1,2],[2,1],[1,3],[3,4],[4,1]]
result = sol.validArrangement(pairs)
assert is_valid(result)  # nested cycle structure
assert Counter(map(tuple, result)) == Counter(map(tuple, pairs))

# Large node values
pairs = [[1000000000,1],[1,500000000]]
result = sol.validArrangement(pairs)
assert is_valid(result)  # verifies hashmap handling
assert Counter(map(tuple, result)) == Counter(map(tuple, pairs))

Test Case Summary

Test Why
Example 1 Validates standard Eulerian path
Example 2 Validates Eulerian cycle
Example 3 Validates branching traversal
Single edge Minimum boundary case
Long chain Tests linear traversal
Eulerian circuit Ensures equal degree handling
Multiple cycles connected Tests Hierholzer cycle stitching
Large node values Ensures hashmap-based implementation

Edge Cases

Eulerian Circuit Instead of Eulerian Path

In some graphs, every node has equal indegree and outdegree. In that case, there is no unique starting node with extra outgoing degree.

A buggy implementation might fail to choose a valid starting node. Our implementation handles this by defaulting to the first pair's start node whenever no special start node exists.

Deeply Nested Cycles

Graphs may contain multiple interconnected cycles. A naive DFS that records nodes too early can produce invalid arrangements or miss edges.

Hierholzer's Algorithm specifically solves this issue by only appending nodes during backtracking, after all outgoing edges have been exhausted. This guarantees correct cycle stitching.

Large Sparse Node Values

Node values can be as large as 10^9. Using arrays indexed directly by node value would waste enormous memory or fail entirely.

Our solution uses hash maps (defaultdict in Python and map in Go), which efficiently support sparse large integers without requiring coordinate compression.