easy Relative Sort Array

Problem Statement

Given two arrays arr1 of length n and arr2 of length m, sort the elements of arr1 such that the relative ordering of items in arr1 is the same as in arr2. Elements that do not appear in arr2 should be placed at the end of arr1 in ascending order.

It is given that elements of arr2 are distinct, and all elements in arr2 are also in arr1.

Examples

Example 1:

• Input: arr1 = [3, 5, 2, 1, 6, 4, 5, 6], arr2 = [5, 6, 4, 1]
• Expected Output: [5, 5, 6, 6, 4, 1, 2, 3]
• Justification: Elements 5, 6, 4 and 1 from arr2 are placed in arr1 first in the same order as in arr2. The remaining elements 2 and 3 are placed at the end in ascending order.

Example 2:

• Input: arr1 = [8, 3, 9, 1, 7, 5], arr2 = [3, 9, 8]
• Expected Output: [3, 9, 8, 1, 5, 7]
• Justification: Elements 3, 9 and 8 from arr2 are placed in arr1 first in the same order as in arr2. Remaining elements 1, 5 and 7 are placed at the end in ascending order.

Example 3:

• Input: arr1 = [10, 10, 7, 10, 7, 9], arr2 = [10, 7]
• Expected Output: [10, 10, 10, 7, 7, 9]
• Justification: Elements 10 and 7 from arr2 are placed in arr1 first in the same order as in arr2. The remaining element 9 is placed at the end in ascending order.

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.

Solution

To solve this problem, we use a counting sort approach to arrange the elements of arr1 based on the order defined by arr2. First, we count the occurrences of each element in arr1 and store these counts in an array. Then, we use the counts to construct the sorted result by placing elements from arr2 in the specified order, followed by the remaining elements in ascending order.

This approach is effective because it leverages counting sort's efficiency for sorting integers when the range of values is not excessively large. By focusing on the order defined by arr2, we ensure that the relative ordering is maintained, and by appending the remaining elements in ascending order, we satisfy the problem's requirements.

Step-by-Step Algorithm

1. Find Maximum Element:

   • Identify the largest element in arr1 to determine the size of the count array.

2. Initialize Count Array:

   • Create an array count of size maxElement + 1 to store the frequency of each element in arr1.
   • The size is maxElement + 1 to accommodate the maximum element's index.

3. Calculate the Frequency of each Element in arr1 Array:

   • Iterate through each element in arr1.
   • For each element, increment the corresponding index in the count array by 1.
   • This step counts the occurrences of each element in arr1.

4. Create Result List:

   • Initialize an empty list result to store the sorted elements.

5. Add Elements from arr2 to Result:

   • Iterate through each element in arr2.
   • For each element, append it to the result list as many times as it appears in the count array.
   • Decrement the corresponding index in the count array by 1 for each appended element.
   • This ensures that elements from arr2 appear in the result in the specified order.

6. Add Remaining Elements to Result:

   • Iterate through the count array from index 0 to maxElement.
   • For each index with a positive count, append the index to the result list as many times as its count.
   • Decrement the count for each appended element.
   • This step ensures that remaining elements not in arr2 are appended in ascending order.

7. Convert Result List to Array:

   • Convert the result list to an array and return it.

Algorithm Walkthrough

• Input:
  • arr1 = [3, 5, 2, 1, 6, 4, 5, 6]
  • arr2 = [5, 6, 4, 1]

1. Find Maximum Element:

   • maxElement is 6.

2. Initialize Count Array:

   • count array is initialized to [0, 0, 0, 0, 0, 0, 0].

3. Populate Count Array:

   • Iterate through arr1:
     • For 3: count becomes [0, 0, 0, 1, 0, 0, 0].
     • For 5: count becomes [0, 0, 0, 1, 0, 1, 0].
     • For 2: count becomes [0, 0, 1, 1, 0, 1, 0].
     • For 1: count becomes [0, 1, 1, 1, 0, 1, 0].
     • For 6: count becomes [0, 1, 1, 1, 0, 1, 1].
     • For 4: count becomes [0, 1, 1, 1, 1, 1, 1].
     • For 5: count becomes [0, 1, 1, 1, 1, 2, 1].
     • For 6: count becomes [0, 1, 1, 1, 1, 2, 2].

4. Create Result List:

   • Initialize result as an empty list.

5. Add Elements from arr2 to Result:

   • Iterate through arr2:
     • For 5: Append 5, count becomes [0, 1, 1, 1, 1, 1, 2], result becomes [5].
     • For 5: Append 5, count becomes [0, 1, 1, 1, 1, 0, 2], result becomes [5, 5].
     • For 6: Append 6, count becomes [0, 1, 1, 1, 1, 0, 1], result becomes [5, 5, 6].
     • For 6: Append 6, count becomes [0, 1, 1, 1, 1, 0, 0], result becomes [5, 5, 6, 6].
     • For 4: Append 4, count becomes [0, 1, 1, 1, 0, 0, 0], result becomes [5, 5, 6, 6, 4].
     • For 1: Append 1, count becomes [0, 0, 1, 1, 0, 0, 0], result becomes [5, 5, 6, 6, 4, 1].

6. Add Remaining Elements to Result:

   • Iterate through the count array:
     • For 2: Append 2, count becomes [0, 0, 0, 1, 0, 0, 0], result becomes [5, 5, 6, 6, 4, 1, 2].
     • For 3: Append 3, count becomes [0, 0, 0, 0, 0, 0, 0], result becomes [5, 5, 6, 6, 4, 1, 2, 3].

7. Convert Result List to Array:

   • result list is converted to array [5, 5, 6, 6, 4, 1, 2, 3].

Code

import java.util.*;

class Solution {

  public int[] relativeSortArray(int[] arr1, int[] arr2) {
    // Determine the largest value in arr1 to size the count array correctly
    int maxElement = Arrays.stream(arr1).max().orElse(0);
    // Create a count array to keep track of occurrences
    int[] count = new int[maxElement + 1];

    // Populate the count array with the frequency of each element in arr1
    for (int element : arr1) {
      count[element]++;
    }

    List<Integer> result = new ArrayList<>();
    // Append elements from arr2 to the result array, maintaining the given order
    for (int value : arr2) {
      while (count[value] > 0) {
        result.add(value);
        count[value]--;
      }
    }

    // Add the remaining elements that are not in arr2 to the result array in ascending order
    for (int num = 0; num <= maxElement; num++) {
      while (count[num] > 0) {
        result.add(num);
        count[num]--;
      }
    }

    // Convert the result ArrayList back to an array and return it
    return result.stream().mapToInt(Integer::intValue).toArray();
  }

  public static void main(String[] args) {
    Solution solution = new Solution();

    // Test case 1
    int[] arr1_1 = { 3, 5, 2, 1, 6, 4, 5, 6 };
    int[] arr2_1 = { 5, 6, 4, 1 };
    System.out.println(
      Arrays.toString(solution.relativeSortArray(arr1_1, arr2_1))
    ); // Expected Output: [5, 5, 6, 6, 4, 1, 2, 3]

    // Test case 2
    int[] arr1_2 = { 8, 3, 9, 1, 7, 5 };
    int[] arr2_2 = { 3, 9, 8 };
    System.out.println(
      Arrays.toString(solution.relativeSortArray(arr1_2, arr2_2))
    ); // Expected Output: [3, 9, 8, 1, 5, 7]

    // Test case 3
    int[] arr1_3 = { 10, 10, 7, 10, 7, 9 };
    int[] arr2_3 = { 10, 7 };
    System.out.println(
      Arrays.toString(solution.relativeSortArray(arr1_3, arr2_3))
    ); // Expected Output: [10, 10, 10, 7, 7, 9]
  }
}

Complexity Analysis

Time Complexity:

• n: Length of arr1.
• m: Length of arr2.
• k: Maximum element in arr1.
• We iterate through arr1 to populate the count array . Then, we iterate through arr2 to construct part of the result . Finally, we iterate through the count array to add remaining elements in ascending order . Hence, the total time complexity is .

Space Complexity:

• k: Maximum element in arr1.
• The space complexity is determined by the size of the count array, which is proportional to the maximum element in arr1. Thus, the space complexity is .