2097. Valid Arrangement of Pairs LeetCode Solution

Last updated: February 26, 2025

In this guide, you will get 2097. Valid Arrangement of Pairs LeetCode Solution with the best time and space complexity. The solution to Valid Arrangement of Pairs problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Valid Arrangement of Pairs solution in C++
Valid Arrangement of Pairs solution in Java
Valid Arrangement of Pairs solution in Python
Additional Resources

2097. Valid Arrangement of Pairs LeetCode Solution image

Problem Statement of 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.

Complexity Analysis

Time Complexity: O(|V| + |E|)
Space Complexity: O(|V| + |E|)

2097. Valid Arrangement of Pairs LeetCode Solution in C++

class Solution {
 public:
  vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
    vector<vector<int>> ans;
    unordered_map<int, stack<int>> graph;
    unordered_map<int, int> outDegree;
    unordered_map<int, int> inDegrees;

    for (const vector<int>& pair : pairs) {
      const int start = pair[0];
      const int end = pair[1];
      graph[start].push(end);
      ++outDegree[start];
      ++inDegrees[end];
    }

    const int startNode = getStartNode(graph, outDegree, inDegrees, pairs);
    euler(graph, startNode, ans);
    ranges::reverse(ans);
    return ans;
  }

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

  void euler(unordered_map<int, stack<int>>& graph, int u,
             vector<vector<int>>& ans) {
    auto& stack = graph[u];
    while (!stack.empty()) {
      const int v = stack.top();
      stack.pop();
      euler(graph, v, ans);
      ans.push_back({u, v});
    }
  }
};
/* code provided by PROGIEZ */

2097. Valid Arrangement of Pairs LeetCode Solution in Java

class Solution {
  public int[][] validArrangement(int[][] pairs) {
    List<int[]> ans = new ArrayList<>();
    Map<Integer, Deque<Integer>> graph = new HashMap<>();
    Map<Integer, Integer> outDegree = new HashMap<>();
    Map<Integer, Integer> inDegrees = new HashMap<>();

    for (int[] pair : pairs) {
      final int start = pair[0];
      final int end = pair[1];
      graph.putIfAbsent(start, new ArrayDeque<>());
      graph.get(start).push(end);
      outDegree.merge(start, 1, Integer::sum);
      inDegrees.merge(end, 1, Integer::sum);
    }

    final int startNode = getStartNode(graph, outDegree, inDegrees, pairs);
    euler(graph, startNode, ans);
    Collections.reverse(ans);
    return ans.stream().toArray(int[][] ::new);
  }

  private int getStartNode(Map<Integer, Deque<Integer>> graph, Map<Integer, Integer> outDegree,
                           Map<Integer, Integer> inDegrees, int[][] pairs) {
    for (final int u : graph.keySet())
      if (outDegree.getOrDefault(u, 0) - inDegrees.getOrDefault(u, 0) == 1)
        return u;
    return pairs[0][0]; // Arbitrarily choose a node.
  }

  private void euler(Map<Integer, Deque<Integer>> graph, int u, List<int[]> ans) {
    Deque<Integer> stack = graph.get(u);
    while (stack != null && !stack.isEmpty()) {
      final int v = stack.pop();
      euler(graph, v, ans);
      ans.add(new int[] {u, v});
    }
  }
}
// code provided by PROGIEZ

2097. Valid Arrangement of Pairs LeetCode Solution in Python

class Solution:
  def validArrangement(self, pairs: list[list[int]]) -> list[list[int]]:
    ans = []
    graph = collections.defaultdict(list)
    outDegree = collections.Counter()
    inDegrees = collections.Counter()

    for start, end in pairs:
      graph[start].append(end)
      outDegree[start] += 1
      inDegrees[end] += 1

    def getStartNode() -> int:
      for u in graph.keys():
        if outDegree[u] - inDegrees[u] == 1:
          return u
      return pairs[0][0]  # Arbitrarily choose a node.

    def euler(u: int) -> None:
      stack = graph[u]
      while stack:
        v = stack.pop()
        euler(v)
        ans.append([u, v])

    euler(getStartNode())
    return ans[::-1]
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents