# Relative Sort Array
**Difficulty:** EASY
[External](https://leetcode.com/problems/relative-sort-array)
Canonical: https://scaleengineer.com/dsa/problems/relative-sort-array
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Counting Sort](https://scaleengineer.com/algorithms/counting-sort)
**Data structures:** Array, Hash Table
**Companies:** [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
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.

**Example 1:**

**Input:** arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
**Output:** [2,2,2,1,4,3,3,9,6,7,19]

**Example 2:**

**Input:** arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
**Output:** [22,28,8,6,17,44]

**Constraints:**

* `1 <= arr1.length, arr2.length <= 1000`
* `0 <= arr1[i], arr2[i] <= 1000`
* All the elements of `arr2` are **distinct**.
* Each `arr2[i]` is in `arr1`.

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. It first iterates through `arr2` to place the common elements in the correct relative order. Then, it performs another pass to find all elements not in `arr2`, sorts them, and appends them to the end.
**Time:** O(N * M), where N is the length of `arr1` and M is the length of `arr2`. The nested loops for finding elements and checking for non-existence dominate the runtime. · **Space:** O(N), where N is the length of `arr1`. This space is used for the `result` and `remaining` lists.
**Pros:** Simple to understand and implement.; Directly follows the problem statement.
**Cons:** Highly inefficient due to multiple nested loops.; Will likely result in a 'Time Limit Exceeded' error for larger inputs.
### Explanation
The brute-force method involves a straightforward, step-by-step implementation of the problem's requirements without optimizing for performance. 

First, we construct the initial part of the sorted array. We iterate through each element in `arr2`, and for each of these elements, we scan the entire `arr1` to find all matching occurrences, which are then added to a result list. This ensures the relative order from `arr2` is maintained.

Next, we need to handle the elements that are in `arr1` but not in `arr2`. We create a separate list for these remaining elements. We iterate through `arr1` again. For each element, we check if it exists in `arr2` by performing another full scan of `arr2`. If it doesn't exist, we add it to our list of remaining elements.

Finally, we sort this list of remaining elements in ascending order and append it to our main result list. The list is then converted into an array to be returned.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        List<Integer> result = new ArrayList<>();
        // Part 1: Add elements from arr1 that are in arr2, in order of arr2
        for (int val2 : arr2) {
            for (int val1 : arr1) {
                if (val1 == val2) {
                    result.add(val1);
                }
            }
        }

        // Part 2: Add elements from arr1 that are not in arr2
        List<Integer> remaining = new ArrayList<>();
        for (int val1 : arr1) {
            boolean found = false;
            for (int val2 : arr2) {
                if (val1 == val2) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                remaining.add(val1);
            }
        }

        // Sort the remaining elements and add to the result
        Collections.sort(remaining);
        result.addAll(remaining);

        // Convert List to array
        int[] finalResult = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            finalResult[i] = result.get(i);
        }
        return finalResult;
    }
}
```
### Algorithm
*   Initialize an empty list `result` to store the sorted elements.
*   Iterate through each element `val2` in `arr2`.
*   For each `val2`, iterate through `arr1`. If an element `val1` in `arr1` is equal to `val2`, add `val1` to the `result` list.
*   Create another list `remaining` for elements from `arr1` not present in `arr2`.
*   Iterate through `arr1`. For each `val1`, perform a linear scan through `arr2` to check for its existence.
*   If `val1` is not found in `arr2`, add it to the `remaining` list.
*   Sort the `remaining` list in ascending order.
*   Append the sorted `remaining` list to the `result` list.
*   Convert the `result` list to an array and return it.

## Custom Sorting with a HashMap
This approach leverages a custom comparator to sort `arr1`. We first create a map to store the desired order of elements present in `arr2`. Then, we use this map within a comparator to define the sorting logic for all elements in `arr1`, handling both elements present in `arr2` and those that are not.
**Time:** O(M + N log N), where N is the length of `arr1` and M is the length of `arr2`. It takes O(M) to build the map and O(N log N) to sort `arr1`. · **Space:** O(M + N). O(M) for the HashMap and O(N) for the boxed `Integer` array needed for the custom sort. The sorting algorithm itself might use additional space (e.g., O(log N) or O(N)).
**Pros:** A general-purpose solution that works even if element values are not constrained to a small range.; Much more efficient than the brute-force approach.
**Cons:** Requires converting the primitive `int[]` to an `Integer[]`, which adds memory and time overhead.; Not as efficient as counting sort when element values are within a small, known range.
### Explanation
A more optimized approach is to define a custom sorting rule and use a standard sorting algorithm. The key is to establish a clear order for any two elements from `arr1`.

1.  **Create an Order Map:** We first need a way to quickly look up the relative order of elements defined by `arr2`. A HashMap is perfect for this. We create a map `orderMap` where keys are the numbers from `arr2` and values are their indices. This map can be built in O(M) time, where M is the length of `arr2`.

2.  **Custom Sort:** We then sort `arr1`. Since Java's `Arrays.sort` for primitive arrays doesn't accept a custom comparator, we first convert `arr1` into an `Integer[]` array. Then, we sort this new array using a custom comparator that implements our logic:
    *   For any two elements `a` and `b`, we check if they exist in our `orderMap`.
    *   **Case 1 (Both in `arr2`):** If both `a` and `b` are in the map, their order is determined by their original indices in `arr2`. We compare `orderMap.get(a)` and `orderMap.get(b)`.
    *   **Case 2 (One in `arr2`):** If only one element is in the map, it must come before the one that isn't.
    *   **Case 3 (Neither in `arr2`):** If neither is in the map, they are 'extra' elements and should be sorted by their natural numerical order.

After sorting, we copy the elements back into the original `int[]` array.

```java
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> orderMap = new HashMap<>();
        for (int i = 0; i < arr2.length; i++) {
            orderMap.put(arr2[i], i);
        }

        Integer[] arr1Boxed = new Integer[arr1.length];
        for (int i = 0; i < arr1.length; i++) {
            arr1Boxed[i] = arr1[i];
        }

        Arrays.sort(arr1Boxed, (a, b) -> {
            boolean aInArr2 = orderMap.containsKey(a);
            boolean bInArr2 = orderMap.containsKey(b);

            if (aInArr2 && bInArr2) {
                return orderMap.get(a) - orderMap.get(b);
            } else if (aInArr2) {
                return -1; // a comes first
            } else if (bInArr2) {
                return 1;  // b comes first
            } else {
                return a - b; // natural order
            }
        });

        for (int i = 0; i < arr1.length; i++) {
            arr1[i] = arr1Boxed[i];
        }
        return arr1;
    }
}
```
### Algorithm
*   Create a `HashMap<Integer, Integer>` called `orderMap` to store the relative order of elements in `arr2`.
*   Iterate through `arr2` and populate the map: `orderMap.put(arr2[i], i)`.
*   Convert the primitive `int[] arr1` to an `Integer[]` array to allow sorting with a custom comparator.
*   Sort the `Integer[]` array using `Arrays.sort` and a custom lambda comparator.
*   The comparator logic for two elements `a` and `b` is:
    *   If both `a` and `b` are in `orderMap`, compare their mapped indices.
    *   If only `a` is in `orderMap`, `a` comes first.
    *   If only `b` is in `orderMap`, `b` comes first.
    *   If neither is in `orderMap`, compare them numerically (`a - b`).
*   Copy the sorted elements from the `Integer[]` array back to the original `int[]` array.

## Counting Sort
This is the most efficient approach, taking advantage of the constraint that element values are between 0 and 1000. It uses a frequency array (a form of counting sort) to count all elements in `arr1` and then reconstructs the array in the desired order in a single pass.
**Time:** O(N + M + C), where N is `arr1.length`, M is `arr2.length`, and C is the range of values (1001). This simplifies to linear time as C is a constant. · **Space:** O(C), where C is the range of values (1001 in this case). This space is for the `counts` array. This is constant space with respect to the input size N and M.
**Pros:** Extremely fast with linear time complexity.; Simple to implement and avoids the overhead of complex data structures or comparators.; Sorts the array in-place (if allowed), saving space.
**Cons:** This approach is only efficient because the range of element values is small and known (0-1000).; It would be impractical for arrays with a very large or unbounded range of values due to high space requirements.
### Explanation
Given the constraint that all numbers are within the range [0, 1000], we can use a counting-based approach for a linear time solution.

1.  **Frequency Count:** We declare an auxiliary array, `counts`, of size 1001. We iterate through `arr1`, and for each number `num`, we increment `counts[num]`. After this pass, `counts[i]` will hold the frequency of the number `i` in `arr1`.

2.  **Reconstruct Array:** We can now rebuild `arr1` in-place. We use an index `i` to keep track of the current position to fill in `arr1`.
    *   **Part 1 (Relative Order):** We iterate through `arr2`. For each number `val` in `arr2`, we know its count from `counts[val]`. We write `val` into `arr1` `counts[val]` times, advancing our index `i` each time. To ensure these numbers are not processed again, we can set `counts[val]` to 0 after we are done with it.
    *   **Part 2 (Remaining Elements):** After processing all numbers from `arr2`, we iterate through our `counts` array from index 0 to 1000. If `counts[num]` is still greater than 0, it means `num` was not in `arr2`. We append `num` to `arr1` `counts[num]` times. Since we iterate from 0 to 1000, these remaining elements are automatically added in ascending order.

This method processes each array and the counts array a constant number of times, leading to a very efficient solution.

```java
class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] counts = new int[1001];
        // Count frequencies of each number in arr1
        for (int num : arr1) {
            counts[num]++;
        }

        int index = 0;
        // Place elements of arr2 in order
        for (int val : arr2) {
            while (counts[val] > 0) {
                arr1[index++] = val;
                counts[val]--;
            }
        }

        // Place remaining elements in ascending order
        for (int num = 0; num < counts.length; num++) {
            while (counts[num] > 0) {
                arr1[index++] = num;
                counts[num]--;
            }
        }

        return arr1;
    }
}
```
### Algorithm
*   Create a frequency array `counts` of size 1001 (for values 0-1000) and initialize it to all zeros.
*   Iterate through `arr1` and populate the `counts` array: for each `num` in `arr1`, increment `counts[num]`.
*   Initialize a pointer `index = 0` for the result array (which will be `arr1` modified in-place).
*   Iterate through `arr2`. For each `val` in `arr2`:
    *   While `counts[val] > 0`, place `val` at `arr1[index++]` and decrement `counts[val]`.
*   Iterate through the `counts` array from `num = 0` to 1000.
    *   While `counts[num] > 0`, place `num` at `arr1[index++]` and decrement `counts[num]`.
*   Return the modified `arr1`.

# Solutions
### Java

```java
class Solution {
public
  int[] relativeSortArray(int[] arr1, int[] arr2) {
    Map<Integer, Integer> pos = new HashMap<>(arr2.length);
    for (int i = 0; i < arr2.length; ++i) {
      pos.put(arr2[i], i);
    }
    int[][] arr = new int[arr1.length][0];
    for (int i = 0; i < arr.length; ++i) {
      arr[i] =
          new int[]{arr1[i], pos.getOrDefault(arr1[i], arr2.length + arr1[i])};
    }
    Arrays.sort(arr, (a, b)->a[1] - b[1]);
    for (int i = 0; i < arr.length; ++i) {
      arr1[i] = arr[i][0];
    }
    return arr1;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> relativeSortArray(vector<int> &arr1, vector<int> &arr2) {
    unordered_map<int, int> pos;
    for (int i = 0; i < arr2.size(); ++i) {
      pos[arr2[i]] = i;
    }
    vector<pair<int, int>> arr;
    for (int i = 0; i < arr1.size(); ++i) {
      int j = pos.count(arr1[i]) ? pos[arr1[i]] : arr2.size();
      arr.emplace_back(j, arr1[i]);
    }
    sort(arr.begin(), arr.end());
    for (int i = 0; i < arr1.size(); ++i) {
      arr1[i] = arr[i].second;
    }
    return arr1;
  }
};

```

### Python

```python
class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]: pos = {x: i for i, x in enumerate(arr2)} return sorted(arr1, key=lambda x: pos . get(x, 1000 + x))

```