Relative Sort Array

• 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.

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.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public int[] relativeSortArray(int[] arr1, int[] arr2) {7        List<Integer> result = new ArrayList<>();8        // Part 1: Add elements from arr1 that are in arr2, in order of arr29        for (int val2 : arr2) {10            for (int val1 : arr1) {11                if (val1 == val2) {12                    result.add(val1);13                }14            }15        }16 17        // Part 2: Add elements from arr1 that are not in arr218        List<Integer> remaining = new ArrayList<>();19        for (int val1 : arr1) {20            boolean found = false;21            for (int val2 : arr2) {22                if (val1 == val2) {23                    found = true;24                    break;25                }26            }27            if (!found) {28                remaining.add(val1);29            }30        }31 32        // Sort the remaining elements and add to the result33        Collections.sort(remaining);34        result.addAll(remaining);35 36        // Convert List to array37        int[] finalResult = new int[result.size()];38        for (int i = 0; i < result.size(); i++) {39            finalResult[i] = result.get(i);40        }41        return finalResult;42    }43}

• 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.

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.

1import java.util.Arrays;2import java.util.HashMap;3import java.util.Map;4 5class Solution {6    public int[] relativeSortArray(int[] arr1, int[] arr2) {7        Map<Integer, Integer> orderMap = new HashMap<>();8        for (int i = 0; i < arr2.length; i++) {9            orderMap.put(arr2[i], i);10        }11 12        Integer[] arr1Boxed = new Integer[arr1.length];13        for (int i = 0; i < arr1.length; i++) {14            arr1Boxed[i] = arr1[i];15        }16 17        Arrays.sort(arr1Boxed, (a, b) -> {18            boolean aInArr2 = orderMap.containsKey(a);19            boolean bInArr2 = orderMap.containsKey(b);20 21            if (aInArr2 && bInArr2) {22                return orderMap.get(a) - orderMap.get(b);23            } else if (aInArr2) {24                return -1; // a comes first25            } else if (bInArr2) {26                return 1;  // b comes first27            } else {28                return a - b; // natural order29            }30        });31 32        for (int i = 0; i < arr1.length; i++) {33            arr1[i] = arr1Boxed[i];34        }35        return arr1;36    }37}

• 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.

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.

1class Solution {2    public int[] relativeSortArray(int[] arr1, int[] arr2) {3        int[] counts = new int[1001];4        // Count frequencies of each number in arr15        for (int num : arr1) {6            counts[num]++;7        }8 9        int index = 0;10        // Place elements of arr2 in order11        for (int val : arr2) {12            while (counts[val] > 0) {13                arr1[index++] = val;14                counts[val]--;15            }16        }17 18        // Place remaining elements in ascending order19        for (int num = 0; num < counts.length; num++) {20            while (counts[num] > 0) {21                arr1[index++] = num;22                counts[num]--;23            }24        }25 26        return arr1;27    }28}