2097. Valid Arrangement of Pairs

Description

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.

 

Solutions

Solution: Eulerian path

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[][]} pairs
 * @return {number[][]}
 */
const validArrangement = function (pairs) {
  const indegreeMap = new Map();
  const outdegreeMap = new Map();
  const graph = new Map();
  const result = [];

  const findFirstNode = () => {
    for (const node of graph.keys()) {
      const inCount = indegreeMap.get(node) ?? 0;
      const outCount = outdegreeMap.get(node) ?? 0;

      if (inCount - outCount === 1) {
        return node;
      }
    }

    return pairs[0][0];
  };

  for (const [start, end] of pairs) {
    if (!graph.has(start)) {
      graph.set(start, []);
    }

    const inCount = indegreeMap.get(start) ?? 0;
    const outCount = outdegreeMap.get(end) ?? 0;

    graph.get(start).push(end);
    indegreeMap.set(start, inCount + 1);
    outdegreeMap.set(end, outCount + 1);
  }

  const firstNode = findFirstNode();

  const euler = node => {
    const stack = graph.get(node) ?? [];

    while (stack.length) {
      const end = stack.pop();

      euler(end);
      result.push([node, end]);
    }
  };

  euler(firstNode);

  return result.reverse();
};