Code Logo

Relative Sort Array

Published at24 Jul 2026
Created by
Easy 1 views
Like0

Given two arrays arr1 and arr2, where arr2 contains distinct elements and each element in arr2 is also in arr1, sort arr1 such that the relative order of items matches that in arr2. Elements not appearing in arr2 should be sorted in ascending order at the end.

Create a hash map from arr2 value to its index position. Sort arr1 with a custom comparator: if both elements are in arr2, compare by their index in arr2. If only one is in arr2, it comes first. If neither is in arr2, sort by value ascending.

This is a stable sorting problem where a reference array determines the order of a subset. The remaining elements follow standard ascending order.

Edge cases include arr2 having all elements (result matches arr2 order), arr2 having no elements (result is arr1 sorted ascending), and empty arrays.

The relative sort problem demonstrates custom ordering based on a reference array. Elements in the reference get ordered by position, while remaining elements follow natural ascending order. The comparator must handle three cases: both in reference, one in reference, or neither.

The custom comparator handles three cases: both elements in the reference array (compare by position), one element in reference (that element comes first), or neither in reference (compare by natural value). This three-case pattern appears in many sorting problems with partial ordering from an external reference.

Example Input & Output

Example 1
Input
[28,6,22,8,44,17],[22,28,8,6]
Output
[22,28,8,6,17,44]
Explanation

arr2 order: 22,28,8,6. Remaining: 17,44.

Example 2
Input
[2,2,1,1],[1,2]
Output
[1,1,2,2]
Explanation

arr2 order: 1 then 2.

Example 3
Input
[1,2,3],[]
Output
[1,2,3]
Explanation

No arr2, sort ascending.

Example 4
Input
[],[]
Output
[]
Explanation

Empty.

Example 5
Input
[2,3,1,3,2,4,6,7,9,2,19],[2,1,4,3,9,6]
Output
[2,2,2,1,4,3,3,9,6,7,19]
Explanation

arr2 order: 2,1,4,3,9,6. Remaining 7,19 sorted.

Algorithm Flow

Recommendation Algorithm Flow for Relative Sort Array

Solution Approach

Sort elements of arr1 according to the order defined in arr2. Elements that are not in arr2 are appended at the end in ascending order. Build a frequency map of arr1, then iterate through arr2 adding elements in order, and finally add remaining elements sorted.

function relativeSortArray(arr1, arr2) {
  var freq = {}, result = [];
  for (var i = 0; i < arr1.length; i++) freq[arr1[i]] = (freq[arr1[i]] || 0) + 1;
  for (var i = 0; i < arr2.length; i++) {
    while (freq[arr2[i]] > 0) { result.push(arr2[i]); freq[arr2[i]]--; }
  }
  var remaining = [];
  for (var key in freq) {
    while (freq[key] > 0) { remaining.push(parseInt(key)); freq[key]--; }
  }
  remaining.sort(function(a, b) { return a - b; });
  return result.concat(remaining);
}

The frequency map counts occurrences. Elements in arr2 are output first in the specified order. Remaining elements are collected and sorted numerically.

Time O(n log n), Space O(n).

Best Answers

java
import java.util.*;
class Solution {
    public int[] solution(int[] arr1, int[] arr2) {
        Map<Integer,Integer> p=new HashMap<>();
        for (int i=0;i<arr2.length;i++) p.put(arr2[i],i);
        return Arrays.stream(arr1).boxed().sorted((a,b)->{
            boolean ap=p.containsKey(a),bp=p.containsKey(b);
            if (ap&&bp) return p.get(a)-p.get(b);
            if (ap) return -1;
            if (bp) return 1;
            return a-b;
        }).mapToInt(i->i).toArray();
    }
}