Problem

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.

Examples

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.

Solution

Method 1 - Using directed graph and track degrees of node

The problem is to find a valid arrangement of pairs such that for every index i where 1 <= i < pairs.length, end[i-1] == start[i]. The approach is to:

  1. Create a directed graph where each pair is represented as an edge from start to end.
  2. Track the in-degrees and out-degrees of each node to identify the start node (a node with out-degree > in-degree).
  3. Utilize Depth-First Search (DFS) to traverse the graph from the start node to obtain a valid path.

Code

Java
public class Solution {
    public int[][] validArrangement(int[][] pairs) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        Map<Integer, Integer> inDegree = new HashMap<>();
        Map<Integer, Integer> outDegree = new HashMap<>();
        
        // Build graph and degree maps
        for (int[] pair : pairs) {
            graph.computeIfAbsent(pair[0], k -> new ArrayList<>()).add(pair[1]);
            outDegree.put(pair[0], outDegree.getOrDefault(pair[0], 0) + 1);
            inDegree.put(pair[1], inDegree.getOrDefault(pair[1], 0) + 1);
        }
        
        // Find start node (where out-degree > in-degree)
        int start = pairs[0][0];
        for (int key : outDegree.keySet()) {
            if (outDegree.get(key) > inDegree.getOrDefault(key, 0)) {
                start = key;
                break;
            }
        }
        
        // Perform a DFS to find a valid arrangement (Eulerian path)
        List<int[]> ans = new ArrayList<>();
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(start);
        
        while (!stack.isEmpty()) {
            int node = stack.peek();
            if (graph.containsKey(node) && !graph.get(node).isEmpty()) {
                stack.push(graph.get(node).remove(graph.get(node).size() - 1));
            } else {
                stack.pop();
                if (!stack.isEmpty()) {
                    ans.add(new int[]{stack.peek(), node});
                }
            }
        }
        
        Collections.reverse(ans);
        return ans.toArray(new int[ans.size()][]);
    }
}
Python
class Solution:
    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
        graph: Dict[int, List[int]] = defaultdict(list)
        in_degree: Dict[int, int] = defaultdict(int)
        out_degree: Dict[int, int] = defaultdict(int)
        
        # Build graph and degree maps
        for u, v in pairs:
            graph[u].append(v)
            out_degree[u] += 1
            in_degree[v] += 1
        
        # Find start node (where out-degree > in-degree)
        start: int = pairs[0][0]
        for node in out_degree:
            if out_degree[node] > in_degree[node]:
                start = node
                break
        
        # Perform a DFS to find a valid arrangement (Eulerian path)
        ans: List[List[int]] = []
        stack: Deque[int] = deque([start])
        
        while stack:
            node: int = stack[-1]
            if graph[node]:
                stack.append(graph[node].pop())
            else:
                stack.pop()
                if stack:
                    ans.append([stack[-1], node])
        
        ans.reverse()
        return ans

Complexity

  • ⏰ Time complexity: O(n), where n is the number of pairs. We traverse the pairs and an Eulerian path in linear time.
  • 🧺 Space complexity: O(n), for storing the graph and the answer.