Valid arrangement of pairs

Array Depth-First Search Graph Theory Eulerian Circuit

66.5% acceptance

Feb 25, 2026

1075

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;


impl Solution {
  pub fn valid_arrangement(pairs: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let mut graph: HashMap<i32, Vec<i32>> = HashMap::new();
    let mut out_deg: HashMap<i32, i32> = HashMap::new();
    let mut in_deg: HashMap<i32, i32> = HashMap::new();

    for p in &pairs {
      graph.entry(p[0]).or_default().push(p[1]);
      graph.entry(p[1]).or_default(); // ensure exists
      *out_deg.entry(p[0]).or_insert(0) += 1;
      *in_deg.entry(p[1]).or_insert(0) += 1;
    }

    // Find start node: node with out_deg - in_deg = 1; fallback any node
    let mut start = pairs[0][0];
    for (&node, &out) in &out_deg {
      let in_ = *in_deg.get(&node).unwrap_or(&0);
      if out - in_ == 1 {
        start = node;
        break;
      }
    }

    // Hierholzer's algorithm (iterative)
    let mut idx: HashMap<i32, usize> = HashMap::new();
    let mut stack = vec![start];
    let mut path: Vec<i32> = Vec::new();

    while !stack.is_empty() {
      let v = *stack.last().unwrap();
      let i = *idx.entry(v).or_insert(0);
      let len = graph.get(&v).map(|g| g.len()).unwrap_or(0);
      if i < len {
        let next = graph[&v][i];
        *idx.entry(v).or_insert(0) += 1;
        stack.push(next);
      } else {
        path.push(stack.pop().unwrap());
      }
    }

    path.reverse();
    path.windows(2).map(|w| vec![w[0], w[1]]).collect()
  }
}