[Leetcode Python Solution] 2097. Valid Arrangement of Pairs

In this technical blog, we’ll dive deep into Leetcode Problem 2097 — Valid Arrangement of Pairs. We will break down the solution step by step, from understanding the problem, modeling it as a graph theory problem, to implementing the solution.

Problem Link: 2097. Valid Arrangement of Pairs

Problem Description

Given a 2D array pairs where pairs[i] = [start, end], you need to rearrange these pairs so that for adjacent pairs [start1, end1] and [start2, end2], the condition end1 == start2 holds.

It is guaranteed that at least one valid arrangement exists.

Examples

Example 1

Input:

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

Output:

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

Explanation:
The arrangement satisfies:

  • end0 = 9 == 9 = start1
  • end1 = 4 == 4 = start2
  • end2 = 5 == 5 = start3

Example 2

Input:

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

Output:

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

Problem Modeling: Eulerian Path Problem

This problem can be modeled as an Eulerian Path Problem in graph theory. Each pair [start, end] is treated as a directed edge from start to end, and we aim to find a path that traverses all edges while satisfying the given condition.

What is an Eulerian Path?

  • Definition: An Eulerian path is a path in a graph that visits every edge exactly once.
  • Conditions:
    1. An Eulerian path exists if and only if there are exactly two nodes in the graph with unbalanced in-degrees and out-degrees:
      • Start node: the node where out-degree - in-degree = 1.
      • End node: the node where in-degree - out-degree = 1.
    2. If all nodes have equal in-degrees and out-degrees, the graph contains an Eulerian circuit, and the path can start at any node.

Solution Approach

1. Graph Construction

Model each pair [start, end] as a directed edge:

  • Nodes: start and end.
  • Edges: Directed edge from start to end.

Simultaneously, calculate the in-degrees and out-degrees of each node to identify the starting node.

2. Finding the Start Node

Using the in-degree and out-degree counts:

  • A node with out-degree - in-degree = 1 is the start node.
  • If no such node exists, the graph contains an Eulerian circuit, and we can start from any node.

3. Using Hierholzer’s Algorithm to Find the Path

Hierholzer’s Algorithm is used to find an Eulerian path:

  1. Start at the chosen node and follow any unvisited edge.
  2. Continue until reaching a dead end (a node with no outgoing edges).
  3. Backtrack and record the path.
  4. Reverse the recorded path to get the correct order.

Implementation

Here’s the complete Python solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
from collections import defaultdict

def validArrangement(pairs):
    # Construct the graph
    graph = defaultdict(list)
    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 the starting node
    start_node = pairs[0][0]  # Default start node
    for node in graph:
        if out_degree[node] - in_degree[node] == 1:
            start_node = node
            break
    
    # Hierholzer's Algorithm
    path = []
    def dfs(current_node):
        while graph[current_node]:
            next_node = graph[current_node].pop()
            dfs(next_node)
            path.append([current_node, next_node])
    
    dfs(start_node)
    return path[::-1]

Code Explanation

Graph Construction

Using defaultdict to store the adjacency list and count the in-degrees and out-degrees:

1
2
3
4
5
6
7
8
graph = defaultdict(list)
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

Finding the Start Node

Based on the rules for Eulerian paths:

1
2
3
4
5
start_node = pairs[0][0]  # Default value
for node in graph:
    if out_degree[node] - in_degree[node] == 1:
        start_node = node
        break

Hierholzer’s Algorithm

Using a recursive DFS to find the Eulerian path:

1
2
3
4
5
6
path = []  # To store the path
def dfs(current_node):
    while graph[current_node]:  # While there are outgoing edges
        next_node = graph[current_node].pop()  # Remove edge
        dfs(next_node)
        path.append([current_node, next_node])  # Record path

Example Execution

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

Graph State

1
2
3
4
11 → 9
 9 → 4
 4 → 5
 5 → 1

Execution Process

  1. Start DFS from node 11:

    • Visit 11 → 9 and remove the edge.
    • Visit 9 → 4 and remove the edge.
    • Visit 4 → 5 and remove the edge.
    • Visit 5 → 1 and remove the edge.

  2. Backtrack to record the path:

    • path = [[5,1], [4,5], [9,4], [11,9]].

  3. Reverse the path for the final result:

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

Time and Space Complexity

  • Time Complexity: O(E), where E is the number of edges.
    • Constructing the graph: O(E).
    • DFS traversal: O(E).
  • Space Complexity: O(E) for storing the adjacency list and result path.

Python Tips and Tricks

1. Closures

A closure allows inner functions to access variables from the outer function, even after the outer function has finished executing.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
def outer():
    x = 10  # Outer variable

    def inner():
        nonlocal x  # Use the outer variable
        x += 1
        print(x)

    return inner

closure_func = outer()  # Returns the inner function
closure_func()  # Outputs 11
closure_func()  # Outputs 12

In the solution, dfs() uses a closure to access and modify the path list without passing it explicitly.

Conclusion

This problem showcases how to model a graph problem as an Eulerian path and use Hierholzer’s algorithm for an efficient solution. Such graph theory techniques provide a robust framework for solving similar problems.

Feel free to leave questions or share your thoughts!