Valid Arrangement of Pairs - Practice Coding Problems

Valid Arrangement of Pairs - Problem

You are given a 0-indexed 2D integer array pairs where pairs[i] = [start_i, end_i].

An arrangement of pairs is valid if for every index i where 1 <= i < pairs.length, we have end_i-1 == start_i.

Return any valid arrangement of pairs.

Note: The inputs will be generated such that there exists a valid arrangement of pairs.

Input & Output

Example 1 — Basic Chain

$ Input: pairs = [[5,1],[4,5],[11,9],[9,4]]

› Output: [[11,9],[9,4],[4,5],[5,1]]

💡 Note: Forms valid chain: 11→9→4→5→1 where each pair's end matches next pair's start (9=9, 4=4, 5=5)

Example 2 — Simple Path

$ Input: pairs = [[1,3],[3,2],[2,1]]

› Output: [[1,3],[3,2],[2,1]]

💡 Note: Already in correct order: 1→3→2→1 forms complete cycle where 3=3 and 2=2

Example 3 — Two Pairs

$ Input: pairs = [[1,2],[2,3]]

› Output: [[1,2],[2,3]]

💡 Note: Simple chain: 1→2→3 where first pair's end (2) equals second pair's start (2)

Constraints

1 ≤ pairs.length ≤ 10⁵
-10⁶ ≤ start_i, end_i ≤ 10⁶
start_i ≠ end_i
No duplicate pairs
There exists a valid arrangement of pairs

Visualization

Tap to expand

Understanding the Visualization

Input Pairs

Given disconnected pairs that need to be arranged

Find Chain

Arrange so each pair's end equals next pair's start

Valid Output

Connected chain where all pairs link together

Key Takeaway

🎯 Key Insight: Model as Eulerian path problem - traverse all edges exactly once in a directed graph

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to model this as finding an Eulerian path in a directed graph. Each pair represents a directed edge, and we need to traverse all edges exactly once. The optimal approach uses DFS after finding the correct starting node (out-degree - in-degree = 1). Time: O(V + E), Space: O(V + E).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Permutation	O(n!×n)	O(n)	Try all possible arrangements until finding a valid one
Eulerian Path (DFS)	O(V + E)	O(V + E)	Model as graph and find Eulerian path using DFS

Brute Force Permutation — Algorithm Steps

Generate all permutations of pairs
For each permutation, check if consecutive pairs connect
Return the first valid arrangement found

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Permutations

Try all possible orderings of pairs

Check Validity

For each arrangement, verify consecutive pairs connect

Return Valid

Return first valid arrangement found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool isValid(int pairs[][2], int n) {
    for (int i = 1; i < n; i++) {
        if (pairs[i-1][1] != pairs[i][0]) {
            return false;
        }
    }
    return true;
}

void swap(int pairs[][2], int i, int j) {
    int temp[2] = {pairs[i][0], pairs[i][1]};
    pairs[i][0] = pairs[j][0];
    pairs[i][1] = pairs[j][1];
    pairs[j][0] = temp[0];
    pairs[j][1] = temp[1];
}

bool nextPermutation(int pairs[][2], int n) {
    int i = n - 2;
    while (i >= 0 && (pairs[i][0] > pairs[i+1][0] || (pairs[i][0] == pairs[i+1][0] && pairs[i][1] >= pairs[i+1][1]))) {
        i--;
    }
    
    if (i < 0) return false;
    
    int j = n - 1;
    while (pairs[j][0] < pairs[i][0] || (pairs[j][0] == pairs[i][0] && pairs[j][1] <= pairs[i][1])) {
        j--;
    }
    
    swap(pairs, i, j);
    
    int left = i + 1, right = n - 1;
    while (left < right) {
        swap(pairs, left, right);
        left++;
        right--;
    }
    
    return true;
}

int main() {
    int pairs[1000][2];
    int n = 0;
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    char* ptr = line + 1; // Skip '['
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            pairs[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip ','
            pairs[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++; // Skip ']'
            n++;
        }
        ptr++;
    }
    
    do {
        if (isValid(pairs, n)) {
            printf("[");
            for (int i = 0; i < n; i++) {
                printf("[%d,%d]", pairs[i][0], pairs[i][1]);
                if (i < n - 1) printf(",");
            }
            printf("]\n");
            return 0;
        }
    } while (nextPermutation(pairs, n));
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n!×n)

Generate n! permutations, check each one takes O(n) time

⚠ Quadratic Growth

Space Complexity

O(n)

Store current permutation and recursion stack

⚡ Linearithmic Space

23.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Permutation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler