Relative Sort Array

class Solution {
public:
    vector<int> sortRelativeToAnother(vector<int>& firstList, vector<int>& secondList) {
        int largestVal = *max_element(firstList.begin(), firstList.end());
        vector<int> frequency(largestVal + 1);

        // Populate frequency array
        for (int num : firstList) {
            frequency[num]++;
        }

        vector<int> sortedArray;
        // Place elements according to the order in secondList
        for (int value : secondList) {
            while (frequency[value] > 0) {
                sortedArray.push_back(value);
                frequency[value]--;
            }
        }
        // Append the rest in sorted manner
        for (int i = 0; i <= largestVal; i++) {
            while (frequency[i] > 0) {
                sortedArray.push_back(i);
                frequency[i]--;
            }
        }
        return sortedArray;
    }
};

This C++ solution implements a method to sort an array (firstList) in the order defined by another array (secondList). The approach utilizes a counting sort mechanism, leveraging a frequency array to efficiently sort the elements according to the specified order. Here’s the process breakdown:

• Determine the largest value in firstList to define the size of the frequency array.
• Populate the frequency array where the index represents numbers from firstList and the value at each index represents the count of occurrences of that number.
• Construct the sortedArray based on the sequence provided in secondList. Each number from secondList is added to sortedArray according to its frequency.
• After placing all elements that appear in secondList, append the remaining elements from firstList that were not in secondList, in ascending order, using the frequency array to guide the placement.

This method proves efficient especially when secondList represents a subset or a different order of the elements in firstList, and it is particularly well-suited for when the range of potential values in firstList is not excessively large compared to the size of the list.

class Solution {

    public int[] sortArrayByOtherArray(int[] primaryArray, int[] referenceArray) {
        int maximumValue = Arrays.stream(primaryArray).max().orElse(0);
        int[] frequency = new int[maximumValue + 1];

        // Calculate frequency of each element in primaryArray
        for (int num : primaryArray) {
            frequency[num]++;
        }

        List<Integer> sortedList = new ArrayList<>();
        // Sort elements by referenceArray order
        for (int elem : referenceArray) {
            while (frequency[elem] > 0) {
                sortedList.add(elem);
                frequency[elem]--;
            }
        }

        // Append remaining elements sorted in numeric order
        for (int i = 0; i <= maximumValue; i++) {
            while (frequency[i] > 0) {
                sortedList.add(i);
                frequency[i]--;
            }
        }

        // Convert List to primitive int array
        return sortedList.stream().mapToInt(i -> i).toArray();
    }
}

This Java program effectively addresses the problem of sorting an array (primaryArray) based on the order defined by another array (referenceArray). The solution involves several clear steps:

1. Determine the maximum value in primaryArray to set up a frequency array with appropriate size.
2. Populate the frequency array with the count of each element in primaryArray.
3. Initialize an empty list sortedList to hold the final sorted elements.
4. Iterate through referenceArray, and for each element, add it to sortedList as many times as it appears in primaryArray by decrementing its count in the frequency array.
5. After processing all elements in referenceArray, any elements not included but present in primaryArray are appended to sortedList. This is done by iterating through the frequency array and adding each element the number of times it appears.
6. Finally, convert sortedList from a list of Integer to a primitive int array.

This approach ensures that elements are sorted first by the order in referenceArray, and then by their natural numerical order for any remaining elements not covered by referenceArray. The use of a frequency array provides an efficient means of tracking and manipulating the count of elements during the sorting process.

class Solution:
    def sortRelative(self, array1: List[int], array2: List[int]) -> List[int]:
        highest_value = max(array1)
        frequency = [0] * (highest_value + 1)

        for num in array1:
            frequency[num] += 1

        ordered_result = []
        for key in array2:
            while frequency[key] > 0:
                ordered_result.append(key)
                frequency[key] -= 1

        for i in range(highest_value + 1):
            while frequency[i] > 0:
                ordered_result.append(i)
                frequency[i] -= 1

        return ordered_result

To solve the "Relative Sort Array" problem in Python, follow these steps to create a custom ordered array based on a reference array:

1. Calculate the maximum value in array1 to determine the size of a frequency array.
2. Initialize a frequency list of zeroes with a length of the maximum value plus one. This serves to count occurrences of each integer in array1.
3. Iterate over array1, and for each number, increment its corresponding index in the frequency list to record the number of occurrences.
4. Create an empty list ordered_result to store the sorted numbers.
5. Iterate over array2 (the reference array). For each element, append it to ordered_result as many times as it appears in array1 while decrementing its count in the frequency list.
6. After processing all elements of array2, append any remaining numbers from array1 that are not in array2 to ordered_result. These numbers are added in ascending order based on their index in the frequency list.

This strategy ensures that elements are sorted primarily by their order in array2, and secondarily, by their usual ascending order if not found in array2. This solution effectively handles cases where elements are repeated and maintains overall order coherency based on the provided reference array.