You are given a 0-indexed 2D integer array pairs
where pairs[i] = [starti, endi]
. An arrangement of pairs
is valid if for every index i
where 1 <= i < pairs.length
, we have endi-1 == starti
.
Return any valid arrangement of pairs
.
Note: The inputs will be generated such that there exists a 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 endi-1 always equals starti. end0 = 9 == 9 = start1 end1 = 4 == 4 = start2 end2 = 5 == 5 = start3
Example 2:
Input: pairs = [[1,3],[3,2],[2,1]] Output: [[1,3],[3,2],[2,1]] Explanation: This is a valid arrangement since endi-1 always equals starti. end0 = 3 == 3 = start1 end1 = 2 == 2 = start2 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 endi-1 always equals starti. end0 = 2 == 2 = start1 end1 = 1 == 1 = start2
Constraints:
1 <= pairs.length <= 105
pairs[i].length == 2
0 <= starti, endi <= 109
starti != endi
- No two pairs are exactly the same.
- There exists a valid arrangement of
pairs
.
Approach 01:
-
C++
-
Python
#include <vector> #include <unordered_map> #include <stack> #include <algorithm> using namespace std; class Solution { public: vector<vector<int>> validArrangement(vector<vector<int>>& pairs) { vector<vector<int>> result; unordered_map<int, stack<int>> adjacencyList; unordered_map<int, int> outDegree; unordered_map<int, int> inDegree; // Build graph and track in-degrees and out-degrees for (const vector<int>& pair : pairs) { int startNode = pair[0]; int endNode = pair[1]; adjacencyList[startNode].push(endNode); ++outDegree[startNode]; ++inDegree[endNode]; } // Get the starting node for Eulerian path int startNode = findStartNode(adjacencyList, outDegree, inDegree, pairs); // Perform Eulerian traversal eulerianTraversal(adjacencyList, startNode, result); // Reverse the result to get the correct order reverse(result.begin(), result.end()); return result; } private: int findStartNode(const unordered_map<int, stack<int>>& adjacencyList, unordered_map<int, int>& outDegree, unordered_map<int, int>& inDegree, const vector<vector<int>>& pairs) { for (const auto& [node, _] : adjacencyList) if (outDegree[node] - inDegree[node] == 1) return node; return pairs[0][0]; // Arbitrarily choose a node. } void eulerianTraversal(unordered_map<int, stack<int>>& adjacencyList, int currentNode, vector<vector<int>>& result) { auto& nodeStack = adjacencyList[currentNode]; while (!nodeStack.empty()) { int nextNode = nodeStack.top(); nodeStack.pop(); eulerianTraversal(adjacencyList, nextNode, result); result.push_back({currentNode, nextNode}); } } };
from collections import defaultdict, deque from typing import List class Solution: def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]: result = [] adjacencyList = defaultdict(deque) outDegree = defaultdict(int) inDegree = defaultdict(int) # Build graph and track in-degrees and out-degrees for startNode, endNode in pairs: adjacencyList[startNode].append(endNode) outDegree[startNode] += 1 inDegree[endNode] += 1 # Get the starting node for Eulerian path startNode = self.findStartNode(adjacencyList, outDegree, inDegree, pairs) # Perform Eulerian traversal self.eulerianTraversal(adjacencyList, startNode, result) # Reverse the result to get the correct order result.reverse() return result def findStartNode(self, adjacencyList, outDegree, inDegree, pairs): for node in adjacencyList: if outDegree[node] - inDegree[node] == 1: return node return pairs[0][0] # Arbitrarily choose a node. def eulerianTraversal(self, adjacencyList, currentNode, result): nodeStack = adjacencyList[currentNode] while nodeStack: nextNode = nodeStack.popleft() self.eulerianTraversal(adjacencyList, nextNode, result) result.append([currentNode, nextNode])
Time Complexity
- Building the graph:
Iterating through all the pairs to populate the adjacency list, out-degree map, and in-degree map takes \(O(E)\), where \(E\) is the number of edges (pairs).
- Finding the start node:
Iterating through the nodes in the adjacency list to find the start node takes \(O(V)\), where \(V\) is the number of distinct nodes in the graph.
- Eulerian traversal:
The recursive Eulerian traversal iterates through all edges exactly once, taking \(O(E)\).
- Reversing the result:
Reversing the result vector takes \(O(E)\) because it contains one entry for each edge.
- Overall Time Complexity:
The overall time complexity is \(O(E + V)\), where \(E\) is the number of edges and \(V\) is the number of nodes.
Space Complexity
- Adjacency list:
The adjacency list uses \(O(E)\) space, as each edge is stored in a stack within the adjacency list.
- Degree maps:
The out-degree and in-degree maps use \(O(V)\) space, as they store one entry per node.
- Recursive call stack:
The Eulerian traversal makes recursive calls proportional to the number of edges, resulting in \(O(E)\) additional space in the worst case.
- Result vector:
The result vector uses \(O(E)\) space, as it stores one entry for each edge.
- Overall Space Complexity:
The overall space complexity is \(O(E + V)\), where \(E\) is the number of edges and \(V\) is the number of nodes.