# Valid Arrangement of Pairs
**Difficulty:** HARD
[External](https://leetcode.com/problems/valid-arrangement-of-pairs)
Canonical: https://scaleengineer.com/dsa/problems/valid-arrangement-of-pairs
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Eulerian Circuit](https://scaleengineer.com/algorithms/eulerian-circuit)
**Data structures:** Graph
**Companies:** [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Snap](https://scaleengineer.com/companies/snap)
---
## 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`.

**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`.

# Approaches
## Brute-Force with Permutations
This approach involves generating every possible ordering (permutation) of the input pairs and checking each one to see if it forms a valid arrangement. A valid arrangement requires that for any two consecutive pairs `[start1, end1]` and `[start2, end2]`, `end1` must equal `start2`.
**Time:** O(N! * N). There are `N!` permutations, and validating each takes `O(N)` time. · **Space:** O(N) for the recursion stack depth.
**Pros:** Conceptually simple to understand.
**Cons:** Extremely inefficient with factorial time complexity.; Guaranteed to cause a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
The core idea is to explore all `N!` permutations of the `pairs` array, where `N` is the number of pairs. We can implement a recursive function that generates these permutations. The function, say `generatePermutations(index, currentPermutation)`, would place each available pair at the current `index` and recurse for the next index. Once a full permutation of size `N` is formed, we validate it. Validation involves iterating from the second pair to the end and checking the condition `pairs[i-1][1] == pairs[i][0]`. Since the problem guarantees that a valid arrangement exists, the first one we find is a valid answer. However, this approach is computationally infeasible for the given constraints.

```java
// Conceptual structure for brute-force. This will time out.
class Solution {
    int[][] result;
    public int[][] validArrangement(int[][] pairs) {
        List<int[]> pairList = new ArrayList<>();
        for (int[] p : pairs) {
            pairList.add(p);
        }
        permute(pairList, 0);
        return result;
    }

    private void permute(List<int[]> arr, int k) {
        if (result != null) return; // Already found a solution
        if (k == arr.size()) {
            if (isValid(arr)) {
                result = new int[arr.size()][2];
                for (int i = 0; i < arr.size(); i++) {
                    result[i] = arr.get(i);
                }
            }
            return;
        }
        for (int i = k; i < arr.size(); i++) {
            Collections.swap(arr, i, k);
            permute(arr, k + 1);
            Collections.swap(arr, k, i); // backtrack
        }
    }

    private boolean isValid(List<int[]> arrangement) {
        for (int i = 1; i < arrangement.size(); i++) {
            if (arrangement.get(i - 1)[1] != arrangement.get(i)[0]) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- 1. Define a recursive helper function `permute(list, start_index)` to generate all permutations of the input `pairs`.
- 2. The base case for the recursion is when `start_index` reaches the end of the list. At this point, a complete permutation has been generated.
- 3. For each generated permutation, check if it's a valid arrangement by iterating from the second pair and ensuring `pair[i-1][1] == pair[i][0]`.
- 4. Since a valid arrangement is guaranteed to exist, the first one found is the answer. Store it and terminate the search.
- 5. The recursive step involves swapping the element at `start_index` with all subsequent elements to explore different orderings, and backtracking after the recursive call.

## Backtracking Search
This is an improvement over the brute-force approach. Instead of generating full permutations and then checking, we build the arrangement one pair at a time. We prune search branches that cannot lead to a valid solution.
**Time:** O(N * k!) or similar exponential complexity, where `k` is the maximum out-degree of any node. This is better than `O(N!)` but still too slow. · **Space:** O(N) for the recursion stack and storing the path.
**Pros:** More efficient than blind permutation generation due to pruning.
**Cons:** Still has an exponential time complexity in the worst case.; Will likely time out for the given constraints.; Implementation can be complex, especially handling cases with duplicate numbers in pairs.
### Explanation
We can model this as finding a path of length `N` in a state-space graph. We start by trying each pair as the first pair in the arrangement. Then, we recursively search for the next pair. If the current path ends with pair `p1`, the next pair `p2` must have `p2.start == p1.end`. We use a boolean array or a bitmask to keep track of which pairs have already been included in the current path to avoid reusing pairs. The search backtracks if it hits a dead end (i.e., no unused pair can be appended). The search terminates successfully when a path of length `N` (using all pairs) is formed.

```java
// Conceptual structure for backtracking. This is also likely to time out.
class Solution {
    int[][] result;
    int n;
    int[][] pairs;

    public int[][] validArrangement(int[][] pairs) {
        this.n = pairs.length;
        this.pairs = pairs;
        boolean[] used = new boolean[n];
        List<int[]> path = new ArrayList<>();

        // Try starting with each pair
        for (int i = 0; i < n; i++) {
            path.add(pairs[i]);
            used[i] = true;
            if (backtrack(path, used)) {
                return result;
            }
            used[i] = false;
            path.remove(path.size() - 1);
        }
        return null; // Should not be reached
    }

    private boolean backtrack(List<int[]> path, boolean[] used) {
        if (path.size() == n) {
            result = path.toArray(new int[n][]);
            return true;
        }

        int[] lastPair = path.get(path.size() - 1);
        int endNode = lastPair[1];

        for (int i = 0; i < n; i++) {
            if (!used[i] && pairs[i][0] == endNode) {
                used[i] = true;
                path.add(pairs[i]);
                if (backtrack(path, used)) {
                    return true;
                }
                path.remove(path.size() - 1);
                used[i] = false; // backtrack
            }
        }

        return false;
    }
}
```
### Algorithm
- 1. Pre-process the pairs to build a map where keys are starting numbers and values are lists of pairs that begin with that number. This allows for efficient lookups of next possible pairs.
- 2. Use a boolean array `used` to track which pairs (by their original index) have been included in the current path.
- 3. Define a recursive function `backtrack(lastPair, currentPath)`.
- 4. The base case: if `currentPath.size()` equals the total number of pairs, a valid arrangement has been found. Store it and return `true`.
- 5. In the recursive step, get the `end` value of the `lastPair`. Find all unused pairs that start with this `end` value.
- 6. For each such candidate pair, add it to the path, mark it as used, and make a recursive call.
- 7. If the recursive call returns `true`, it means a solution was found down that branch, so propagate `true` upwards.
- 8. If the call returns `false`, backtrack by removing the pair from the path and unmarking it as used.
- 9. To start the process, iterate through all pairs, trying each one as the first pair in the arrangement.

## Eulerian Path (Hierholzer's Algorithm)
The problem can be modeled as finding an Eulerian path in a directed graph. The numbers are vertices, and each pair `[start, end]` is a directed edge from `start` to `end`. An Eulerian path visits every edge exactly once. Since the problem guarantees a solution exists, we just need to find this path using a standard algorithm like Hierholzer's.
**Time:** O(N), where `N` is the number of pairs. Each step (building graph, finding start, traversing) takes time proportional to the number of edges (`N`) and vertices (`U`). · **Space:** O(N). The adjacency list, degree map, and path/stack all require space proportional to the number of pairs `N` and unique nodes `U` (where `U <= 2N`).
**Pros:** Highly efficient with linear time complexity.; Guaranteed to find the solution correctly and quickly.; It's the standard, optimal algorithm for this type of problem.
**Cons:** Requires knowledge of graph theory (Eulerian paths).; Implementation is more involved than naive approaches.
### Explanation
**1. Graph Representation:** We first build a graph. An adjacency list, represented by a `Map<Integer, Deque<Integer>>`, is suitable. The keys are the source vertices, and the values are deques of destination vertices. We also compute the in-degrees and out-degrees of all vertices to find the starting point of the path. A `Map<Integer, Integer> degree` can store `out-degree - in-degree`.

**2. Finding the Start Node:** An Eulerian path starts at a vertex `v` where `out-degree(v) - in-degree(v) = 1`. If no such vertex exists, the graph has an Eulerian circuit, and any vertex can be a starting point. We iterate through our degree map to find this special start node. If not found, we can default to `pairs[0][0]`.

**3. Path Finding (Hierholzer's Algorithm):** We use a post-order DFS traversal. An iterative approach with a stack is common.
- Push the start node onto a stack.
- While the stack is not empty, look at the top vertex `u`.
- If `u` has unvisited outgoing edges, pick one (e.g., `u -> v`), push `v` onto the stack, and remove the edge `u -> v` from the graph to mark it as visited.
- If `u` has no more outgoing edges, pop it from the stack and add it to a result list `path`.

**4. Final Arrangement:** The `path` list we constructed contains the sequence of vertices in reverse order. We reverse it to get the correct path. Then, we construct the final `int[][]` result by creating pairs `[path[i], path[i+1]]` for `i` from 0 to `path.length - 2`.

```java
import java.util.*;

class Solution {
    public int[][] validArrangement(int[][] pairs) {
        int n = pairs.length;
        Map<Integer, Deque<Integer>> adj = new HashMap<>();
        Map<Integer, Integer> degree = new HashMap<>();

        for (int[] pair : pairs) {
            int u = pair[0];
            int v = pair[1];
            adj.computeIfAbsent(u, k -> new ArrayDeque<>()).add(v);
            degree.put(u, degree.getOrDefault(u, 0) + 1);
            degree.put(v, degree.getOrDefault(v, 0) - 1);
        }

        int startNode = -1;
        for (Map.Entry<Integer, Integer> entry : degree.entrySet()) {
            if (entry.getValue() == 1) {
                startNode = entry.getKey();
                break;
            }
        }

        if (startNode == -1) {
            // It's an Eulerian circuit, start from any node with an edge
            startNode = pairs[0][0];
        }

        List<Integer> path = new ArrayList<>();
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(startNode);

        while (!stack.isEmpty()) {
            int u = stack.peek();
            if (adj.containsKey(u) && !adj.get(u).isEmpty()) {
                int v = adj.get(u).pop();
                stack.push(v);
            } else {
                path.add(stack.pop());
            }
        }

        Collections.reverse(path);

        int[][] result = new int[n][2];
        for (int i = 0; i < n; i++) {
            result[i][0] = path.get(i);
            result[i][1] = path.get(i + 1);
        }

        return result;
    }
}
```
### Algorithm
- 1. **Build Graph and Degrees:**
  - Create an adjacency list `adj` (e.g., `Map<Integer, Deque<Integer>>`) to store the graph.
  - Create a degree map `degree` (e.g., `Map<Integer, Integer>`) to store `out-degree - in-degree` for each node.
  - Iterate through each pair `[u, v]`: add an edge `u -> v` to `adj`, increment `degree[u]`, and decrement `degree[v]`.
- 2. **Find Start Node:**
  - The start node of the Eulerian path is the unique node with `degree == 1`.
  - Iterate through the `degree` map to find this node.
  - If no such node exists, the graph has an Eulerian circuit. Any node with outgoing edges can be the start node (e.g., `pairs[0][0]`)
- 3. **Hierholzer's Algorithm (Iterative DFS):**
  - Use a `stack` for the traversal and a `path` list to store the result.
  - Push the `startNode` onto the `stack`.
  - While the `stack` is not empty:
      - Peek at the current node `u` on top of the stack.
      - If `u` has any unvisited outgoing edges (i.e., `adj.get(u)` is not empty), pop an edge `u -> v`, and push `v` onto the stack.
      - If `u` has no more outgoing edges, pop `u` from the stack and add it to the `path` list.
- 4. **Construct Final Result:**
  - The `path` list is generated in reverse post-order. Reverse it to get the correct vertex sequence.
  - Create the final `int[][]` arrangement by taking consecutive nodes from the `path` list: `[path.get(i), path.get(i+1)]`.