We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Valid Arrangement of Pairs

Number: 2201

Difficulty: Hard

Paid? No

Companies: Meta, Goldman Sachs

Problem Description

Given a list of pairs where each pair represents a directed edge between two nodes, arrange the pairs in such a way that for every consecutive pair in the resulting sequence, the end of the previous pair equals the start of the next. It is guaranteed that such an arrangement exists.

Key Insights

  • Interpret each pair as a directed edge from start to end.
  • The problem reduces to finding an Eulerian path (or circuit) in a directed graph.
  • If a vertex exists with out-degree exactly one greater than in-degree, it should be the starting vertex; otherwise, any vertex can serve as a valid starting node.
  • Hierholzer’s algorithm is ideal to reconstruct an Eulerian path by performing a modified DFS that “peels off” cycles and ensures all edges get used exactly once.

Space and Time Complexity

Time Complexity: O(N), where N is the number of pairs since every edge is visited exactly once. Space Complexity: O(N) for storing the graph and the recursion/stack space for DFS.

Solution

We first build a graph mapping each start node to a list of its end nodes. To efficiently obtain and remove edges, sort each list in reverse order so that we can “pop” from the end. Next, determine a valid starting node: if there is a vertex whose out-degree is exactly one more than its in-degree, start from there. Otherwise, we pick any vertex that exists in the graph.

Using Hierholzer’s algorithm, perform a DFS:

  1. While the current vertex has outgoing edges, pop the last edge (which is efficient thanks to our reverse-sorted order) and recursively visit the end node.
  2. Append the current vertex to the path once all its edges are visited.
  3. Finally, reverse the recorded path to obtain the Eulerian path.

This path will be a list of vertices. To convert it back into a list of pairs, form pairs from consecutive vertices. Since each pair is exactly the edge used in the Eulerian path and all pairs are unique, this fulfills the problem's requirements.

Code Solutions

# Build the graph, find the Eulerian path, and convert the path to the valid arrangement of pairs.
from collections import defaultdict, deque

def validArrangement(pairs):
    graph = defaultdict(list)
    in_degree = defaultdict(int)
    out_degree = defaultdict(int)
    
    # Build graph and degree count
    for start, end in pairs:
        graph[start].append(end)
        out_degree[start] += 1
        in_degree[end] += 1
    
    # Sort each list in reverse order for efficient pop
    for start in graph:
        graph[start].sort(reverse=True)
    
    # Find start node: node with out-degree = in-degree + 1, else any node with outgoing edge.
    start_node = pairs[0][0]
    for node in out_degree:
        if out_degree[node] - in_degree[node] == 1:
            start_node = node
            break

    path = []
    def dfs(node):
        while graph[node]:
            next_node = graph[node].pop()
            dfs(next_node)
        path.append(node)
    
    dfs(start_node)
    path.reverse()
    
    # Convert vertex path to pairs. Since path is a list of vertices, each consecutive pair forms an edge.
    arrangement = []
    for i in range(1, len(path)):
        arrangement.append([path[i-1], path[i]])
    return arrangement

# Example usage:
pairs_example = [[5,1],[4,5],[11,9],[9,4]]
print(validArrangement(pairs_example))
← Back to All Questions