Find original array from doubled array

Array Hash Table Greedy Sorting

40.7% acceptance

Feb 25, 2026

2562

120

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array. Given an array changed, return original if changed is a doubled array, or an empty array if it is not possible.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_original_array(changed: Vec<i32>) -> Vec<i32> {
    if changed.len() % 2 != 0 { return vec![]; }
    let mut sorted = changed.clone();
    sorted.sort();
    
    use std::collections::BTreeMap;
    let mut cnt: BTreeMap<i32, i32> = BTreeMap::new();
    for &v in &sorted { *cnt.entry(v).or_insert(0) += 1; }
    
    let mut ans = vec![];
    for &v in &sorted {
      if *cnt.get(&v).unwrap_or(&0) == 0 { continue; }
      *cnt.get_mut(&v).unwrap() -= 1;
      let dbl = v * 2;
      if *cnt.get(&dbl).unwrap_or(&0) == 0 { return vec![]; }
      *cnt.get_mut(&dbl).unwrap() -= 1;
      ans.push(v);
    }
    ans
  }
}