2097. 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.

Approach 01:

#include <vector>
#include <unordered_map>
#include <stack>
#include <algorithm>

using namespace std;

class Solution {
 public:
  vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
    vector<vector<int>> result;
    unordered_map<int, stack<int>> adjacencyList;
    unordered_map<int, int> outDegree;
    unordered_map<int, int> inDegree;

    // Build graph and track in-degrees and out-degrees
    for (const vector<int>& pair : pairs) {
      int startNode = pair[0];
      int endNode = pair[1];
      adjacencyList[startNode].push(endNode);
      ++outDegree[startNode];
      ++inDegree[endNode];
    }

    // Get the starting node for Eulerian path
    int startNode = findStartNode(adjacencyList, outDegree, inDegree, pairs);

    // Perform Eulerian traversal
    eulerianTraversal(adjacencyList, startNode, result);

    // Reverse the result to get the correct order
    reverse(result.begin(), result.end());
    return result;
  }

 private:
  int findStartNode(const unordered_map<int, stack<int>>& adjacencyList,
                    unordered_map<int, int>& outDegree,
                    unordered_map<int, int>& inDegree,
                    const vector<vector<int>>& pairs) {
    for (const auto& [node, _] : adjacencyList)
      if (outDegree[node] - inDegree[node] == 1)
        return node;
    return pairs[0][0];  // Arbitrarily choose a node.
  }

  void eulerianTraversal(unordered_map<int, stack<int>>& adjacencyList, int currentNode,
                         vector<vector<int>>& result) {
    auto& nodeStack = adjacencyList[currentNode];
    while (!nodeStack.empty()) {
      int nextNode = nodeStack.top();
      nodeStack.pop();
      eulerianTraversal(adjacencyList, nextNode, result);
      result.push_back({currentNode, nextNode});
    }
  }
};

from collections import defaultdict, deque
from typing import List

class Solution:
    def validArrangement(self, pairs: List[List[int]]) -> List[List[int]]:
        result = []
        adjacencyList = defaultdict(deque)
        outDegree = defaultdict(int)
        inDegree = defaultdict(int)

        # Build graph and track in-degrees and out-degrees
        for startNode, endNode in pairs:
            adjacencyList[startNode].append(endNode)
            outDegree[startNode] += 1
            inDegree[endNode] += 1

        # Get the starting node for Eulerian path
        startNode = self.findStartNode(adjacencyList, outDegree, inDegree, pairs)

        # Perform Eulerian traversal
        self.eulerianTraversal(adjacencyList, startNode, result)

        # Reverse the result to get the correct order
        result.reverse()
        return result

    def findStartNode(self, adjacencyList, outDegree, inDegree, pairs):
        for node in adjacencyList:
            if outDegree[node] - inDegree[node] == 1:
                return node
        return pairs[0][0]  # Arbitrarily choose a node.

    def eulerianTraversal(self, adjacencyList, currentNode, result):
        nodeStack = adjacencyList[currentNode]
        while nodeStack:
            nextNode = nodeStack.popleft()
            self.eulerianTraversal(adjacencyList, nextNode, result)
            result.append([currentNode, nextNode])

Time Complexity

• Building the graph:

  Iterating through all the pairs to populate the adjacency list, out-degree map, and in-degree map takes \(O(E)\), where \(E\) is the number of edges (pairs).

• Finding the start node:

  Iterating through the nodes in the adjacency list to find the start node takes \(O(V)\), where \(V\) is the number of distinct nodes in the graph.

• Eulerian traversal:

  The recursive Eulerian traversal iterates through all edges exactly once, taking \(O(E)\).

• Reversing the result:

  Reversing the result vector takes \(O(E)\) because it contains one entry for each edge.

• Overall Time Complexity:

  The overall time complexity is \(O(E + V)\), where \(E\) is the number of edges and \(V\) is the number of nodes.

Space Complexity

• Adjacency list:

  The adjacency list uses \(O(E)\) space, as each edge is stored in a stack within the adjacency list.

• Degree maps:

  The out-degree and in-degree maps use \(O(V)\) space, as they store one entry per node.

• Recursive call stack:

  The Eulerian traversal makes recursive calls proportional to the number of edges, resulting in \(O(E)\) additional space in the worst case.

• Result vector:

  The result vector uses \(O(E)\) space, as it stores one entry for each edge.

• Overall Space Complexity:

  The overall space complexity is \(O(E + V)\), where \(E\) is the number of edges and \(V\) is the number of nodes.