Relative sort array

Array Hash Table Sorting Counting Sort

75.1% acceptance

Feb 25, 2026

3345

199

Given two arrays arr1 and arr2, the elements of arr2 are distinct, and all elements in arr2 are also in arr1. Sort the elements of arr1 such that the relative ordering of items in arr1 are the same as in arr2. Elements that do not appear in arr2 should be placed at the end of arr1 in ascending order.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn relative_sort_array(arr1: Vec<i32>, arr2: Vec<i32>) -> Vec<i32> {
    use std::collections::HashMap;
    let order: HashMap<i32, usize> = arr2.iter().enumerate().map(|(i, &v)| (v, i)).collect();
    let mut in_arr2: Vec<i32> = arr1.iter().filter(|&&x| order.contains_key(&x)).cloned().collect();
    let mut not_in_arr2: Vec<i32> = arr1.iter().filter(|&&x| !order.contains_key(&x)).cloned().collect();
    in_arr2.sort_by_key(|x| order[x]);
    not_in_arr2.sort();
    in_arr2.extend(not_in_arr2);
    in_arr2
  }
}