Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

2201. Valid Arrangement of Pairs

My accepted Python solution to LeetCode problem 2201, Valid Arrangement of Pairs, running in 549ms.

  • Difficulty: Hard
  • Python
  • Runtime 549ms
  • Memory 141.8MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 549ms, memory 141.8MB, accepted 2025-12-29.

python
class Solution:
    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
        # Eulerian Path problem - use Hierholzer's algorithm
        # Time: O(E), Space: O(E)
        from collections import defaultdict, deque
        
        # Build adjacency list and calculate degrees
        graph = defaultdict(deque)
        in_degree = defaultdict(int)
        out_degree = defaultdict(int)
        
        for start, end in pairs:
            graph[start].append(end)
            out_degree[start] += 1
            in_degree[end] += 1
        
        # Find starting node (out_degree - in_degree == 1, or any node)
        start_node = pairs[0][0]
        for node in graph:
            if out_degree[node] - in_degree[node] == 1:
                start_node = node
                break
        
        # Hierholzer's algorithm
        path = []
        stack = [start_node]
        
        while stack:
            while graph[stack[-1]]:
                next_node = graph[stack[-1]].popleft()
                stack.append(next_node)
            path.append(stack.pop())
        
        path.reverse()
        
        # Build result
        result = []
        for i in range(len(path) - 1):
            result.append([path[i], path[i + 1]])
        
        return result

Source