2097. Valid Arrangement of Pairs

Problem

You are given a 0-indexed 2D integer array pairs where pairs[i] = [startᵢ, endᵢ]. An arrangement of pairs is valid if for every index i where 1 <= i < pairs.length, we have endᵢ₋₁ == startᵢ.

Return any valid arrangement of pairs.

Note: The inputs will be generated such that there exists a valid arrangement of pairs.

https://leetcode.com/problems/valid-arrangement-of-pairs/

Example 1:

Input: pairs = [[5,1],[4,5],[11,9],[9,4]]
Output: [[11,9],[9,4],[4,5],[5,1]]
Explanation:
This is a valid arrangement since endᵢ₋₁ always equals startᵢ.
end₀ = 9 == 9 = start₁
end₁ = 4 == 4 = start₂
end₂ = 5 == 5 = start₃

Example 2:

Input: pairs = [[1,3],[3,2],[2,1]]
Output: [[1,3],[3,2],[2,1]]
Explanation:
This is a valid arrangement since endᵢ₋₁ always equals startᵢ.
end₀ = 3 == 3 = start₁
end₁ = 2 == 2 = start₂
The arrangements [[2,1],[1,3],[3,2]] and [[3,2],[2,1],[1,3]] are also valid.

Example 3:

Input: pairs = [[1,2],[1,3],[2,1]]
Output: [[1,2],[2,1],[1,3]]
Explanation:
This is a valid arrangement since endᵢ₋₁ always equals startᵢ.
end₀ = 2 == 2 = start₁
end₁ = 1 == 1 = start₂

Constraints:

1 <= pairs.length <= 10⁵
pairs[i].length == 2
0 <= startᵢ, endᵢ <= 10⁹
startᵢ != endᵢ
No two pairs are exactly the same.
There exists a valid arrangement of pairs.

Test Cases

1 2	class Solution: def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:

solution_test.py

import itertools
import pytest

from solution import Solution


@pytest.mark.parametrize('pairs, expected', [
    ([[5,1],[4,5],[11,9],[9,4]], [[11,9],[9,4],[4,5],[5,1]]),
    ([[1,3],[3,2],[2,1]], [[1,3],[3,2],[2,1]]),
    ([[1,2],[1,3],[2,1]], [[1,2],[2,1],[1,3]]),

    (
        [[5,13],[10,6],[11,3],[15,19],[16,19],[1,10],[19,11],[4,16],[19,9],[5,11],[5,6],[13,5],[13,9],[9,15],[11,16],[6,9],[9,13],[3,1],[16,5],[6,5]],
        [[4,16],[16,5],[5,6],[6,5],[5,11],[11,16],[16,19],[19,9],[9,13],[13,5],[5,13],[13,9],[9,15],[15,19],[19,11],[11,3],[3,1],[1,10],[10,6],[6,9]]
    ),
])
class Test:
    def test_solution(self, pairs, expected):
        sol = Solution()
        result = sol.validArrangement(pairs.copy())
        assert sorted(result) == sorted(pairs)
        assert self._is_valid(result)

    def _is_valid(self, pairs):
        for a, b in itertools.pairwise(pairs):
            if a[1] != b[0]:
                return False

        return True

Thoughts

以每个数字作为顶点，对于 pairs[i] = [startᵢ, endᵢ]，作 startᵢ 到 endᵢ 的有向边，构成有向图。

显然题目所求就是图中的欧拉通路。也就是「一笔画」问题。

欧拉通路：通过图中所有边一次且仅一次行遍所有顶点的通路。

A directed graph has an Eulerian trail if and only if at most one vertex has (out-degree) − (in-degree) = 1, at most one vertex has (in-degree) − (out-degree) = 1, every other vertex has equal in-degree and out-degree. [wiki]

求欧拉通路一般有两个算法：Fleury’s algorithm 和 Hierholzer’s algorithm，后者效率要高得多。

用 Hierholzer 算法。

首先如果存在 (out-degree) − (in-degree) = 1 和 (in-degree) − (out-degree) = 1 的顶点，记为 u₀ 和 v₀。它俩是欧拉通路的起点和终点。如果不存在，则有欧拉回路，可以从任何顶点断开得到欧拉通路。

如果存在 u₀ 则取它，否则任取一个顶点 u，出发遍历图，每经过一条边就从边集中删除，直到遍历到某个顶点没有任何出边。显然如果是从 u₀ 出发，最后一定会停在 v₀，否则一定会回到 u。

如果没有剩余的边了，则已经得到了欧拉通路（或回路）。否则看已有路径中的每个顶点，一定存在某个顶点有不在当前路径的边，从这个顶点（记为 u'）出发，直到再次回到 u'。把新得到的回路加入到原来的路径中，即 u -> 原路径前半段 -> u' -> 刚找到的回路 -> u' -> 原路径后半段 -> u。

图的存储用邻接表法，也便于遍历的时候删除访问过的边。整个邻接表用哈希表记录，当一个顶点的所有出边都处理完，可以将该顶点删除，以便快速判断是否还有未访问到的边。用链表记录已经找到的通路，以便可以和之后找到的回路合并。再用一个字典索引当前通路中各个顶点所在的链表节点，以便快速找到新回路的接入位置。

时间复杂度 O(E)，E 是图中边的数量，即 pairs 的长度。

Code

solution.py

from collections import defaultdict


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __repr__(self) -> str:
        next = str(self.next.val) if self.next else 'X'
        return f'{self.val} -> {next}'


class Solution:
    def validArrangement(self, pairs: list[list[int]]) -> list[list[int]]:
        graph: dict[int, list[int]] = defaultdict(list) # vertex: list of its successor.
        degrees: dict[int, int] = defaultdict(int) # vertex: its (out-degree) - (in-degree).
        for u, v in pairs:
            graph[u].append(v)
            degrees[u] += 1
            degrees[v] -= 1

        u0 = next((u for u, d in degrees.items() if d == 1), pairs[0][0])
        root = ListNode(u0) # Root of the full Eulerian trail.
        indexes = {u0: root} # vertex: one of its occurrence in Eulerian trail.
        u = u0
        while u is not None:
            node = indexes[u]
            further = node.next

            # Find a trail starting from u.
            while u in graph:
                vs = graph[u]
                v = vs.pop()
                node.next = node = indexes[v] = ListNode(v)
                if not vs:
                    del graph[u]

                u = v

            node.next = further
            u = next((u for u in graph if u in indexes), None)

        result = [None] * len(pairs)
        node = root
        i = 0
        while node.next:
            result[i] = [node.val, node.next.val]
            node = node.next
            i += 1

        return result