Scale Engineer

Valid Arrangement of Pairs

Hard
#1909Time: O(N! * N). There are `N!` permutations, and validating each takes `O(N)` time.Space: O(N) for the recursion stack depth.2 companies
Algorithms
Depth-First SearchEulerian Circuit
Data structures
Graph
Companies
Goldman SachsSnap

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

Algorithm

    1. Define a recursive helper function permute(list, start_index) to generate all permutations of the input pairs.
    1. 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.
    1. 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].
    1. Since a valid arrangement is guaranteed to exist, the first one found is the answer. Store it and terminate the search.
    1. The recursive step involves swapping the element at start_index with all subsequent elements to explore different orderings, and backtracking after the recursive call.

Walkthrough

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.

// 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;    }}

Complexity

Time

O(N! * N). There are `N!` permutations, and validating each takes `O(N)` time.

Space

O(N) for the recursion stack depth.

Trade-offs

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.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem