{x}
blog image

Valid Arrangement of Pairs

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.

Solution Explanation: Finding a Valid Arrangement of Pairs

This problem involves finding a valid arrangement of pairs, where each pair's end element equals the next pair's start element. This is essentially finding an Eulerian path (or circuit) in a directed graph.

Approach:

  1. Build an Adjacency List: Create a directed graph where each unique number in the pairs array represents a node. An edge from node u to node v exists if the pair [u, v] is present. We use a dictionary (or hash map) to store the adjacency list efficiently.

  2. Find the Starting Node: Determine the starting node for our path. This is the node with an in-degree (number of incoming edges) less than its out-degree (number of outgoing edges). This is because in an Eulerian path, the starting node has one more outgoing edge than incoming edges. If all nodes have equal in-degree and out-degree, then we have an Eulerian circuit and any node can be the start.

  3. Depth-First Search (DFS): Perform a Depth-First Search (DFS) to traverse the graph and construct the valid arrangement. During the DFS, we keep track of the visited edges.

  4. Reverse the Path: The DFS will give us a path in reverse order. Reverse the resulting path to obtain the correct valid arrangement.

Time Complexity Analysis:

  • Building the adjacency list: O(N), where N is the length of pairs.
  • Finding the starting node: O(V), where V is the number of unique nodes (vertices) in the graph.
  • Depth-First Search (DFS): O(E), where E is the number of edges in the graph (which is equal to N).
  • Reversing the path: O(N).

Therefore, the overall time complexity is dominated by the DFS and is O(N).

Space Complexity Analysis:

  • Adjacency list: O(V + E), which is O(N) in the worst case.
  • Stack during DFS: O(N) in the worst case (for a graph with a long path).
  • Resulting path: O(N).

The overall space complexity is O(N).

Code Implementation (Python):

from collections import defaultdict
 
def validArrangement(pairs):
    graph = defaultdict(list)
    in_degree = defaultdict(int)
    out_degree = defaultdict(int)
    nodes = set()
 
    for u, v in pairs:
        graph[u].append(v)
        out_degree[u] += 1
        in_degree[v] += 1
        nodes.add(u)
        nodes.add(v)
 
 
    start_node = next((node for node in nodes if out_degree[node] > in_degree[node]),list(nodes)[0]) #Finds a starting node, or picks the first if it is an Eulerian circuit
 
 
    path = []
    visited = set()
 
    def dfs(node):
        for neighbor in graph[node]:
            edge = (node, neighbor)
            if edge not in visited:
                visited.add(edge)
                dfs(neighbor)
        path.append(node)
 
    dfs(start_node)
    return [[path[i], path[i+1]] for i in range(len(path)-1)][::-1]

Code Implementation (Java):

import java.util.*;
 
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<>();
        Set<Integer> nodes = new HashSet<>();
 
        for (int[] pair : pairs) {
            int u = pair[0];
            int v = pair[1];
            graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
            outDegree.put(u, outDegree.getOrDefault(u, 0) + 1);
            inDegree.put(v, inDegree.getOrDefault(v, 0) + 1);
            nodes.add(u);
            nodes.add(v);
        }
 
        int startNode = nodes.iterator().next(); //Arbitrary start if Eulerian circuit, otherwise below line would find a better one
        for (int node : nodes) {
            if (outDegree.getOrDefault(node, 0) > inDegree.getOrDefault(node, 0)) {
                startNode = node;
                break;
            }
        }
 
        List<Integer> path = new ArrayList<>();
        Set<Pair> visited = new HashSet<>();
 
        dfs(startNode, graph, visited, path);
        Collections.reverse(path);
 
 
        int[][] result = new int[path.size() -1][2];
        for (int i = 0; i < path.size() - 1; i++) {
            result[i][0] = path.get(i);
            result[i][1] = path.get(i + 1);
        }
        return result;
    }
 
 
    private void dfs(int node, Map<Integer, List<Integer>> graph, Set<Pair> visited, List<Integer> path) {
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            Pair edge = new Pair(node, neighbor);
            if (!visited.contains(edge)) {
                visited.add(edge);
                dfs(neighbor, graph, visited, path);
            }
        }
        path.add(node);
    }
 
    private static class Pair {
        int u;
        int v;
 
        Pair(int u, int v) {
            this.u = u;
            this.v = v;
        }
 
        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (obj == null || getClass() != obj.getClass()) return false;
            Pair other = (Pair) obj;
            return u == other.u && v == other.v;
        }
 
        @Override
        public int hashCode() {
            return Objects.hash(u, v);
        }
    }
}

This detailed explanation and code examples should provide a clear understanding of how to solve the "Valid Arrangement of Pairs" problem efficiently. Remember to handle edge cases (like empty input) in a production-ready solution.