Code Logo

Relative Sort Array

Published at24 Jul 2026
Created by
Easy 0 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
Recommendation Algorithm Flow for Relative Sort Array

Solution Approach

Build position map from arr2. Sort arr1: if both in map, compare positions; else sort by value.

function solution(arr1, arr2) {
  var pos = {};
  for (var i = 0; i < arr2.length; i++) pos[arr2[i]] = i;
  arr1.sort(function(a, b) {
    if (pos[a] !== undefined && pos[b] !== undefined) return pos[a] - pos[b];
    if (pos[a] !== undefined) return -1;
    if (pos[b] !== undefined) return 1;
    return a - b;
  });
  return arr1;
}

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();
    }
}