easy Relative Sort Array

Problem Statement

You are given two integers arrays arr1 and arr2. All elements of the arr2 are distinct, and present in arr1.

Sort the array arr1 such that relative orders of elements of arr1 should be the same as in arr2. If any elements in arr1 not found in arr2 should come at the end, sorted in ascending order.

Examples

Example 1:

• Input: arr1 = [8, 1, 2, 3, 4, 8, 9], arr2 = [4, 3, 2, 1]
• Expected Output: [4, 3, 2, 1, 8, 8, 9]
• Justification: The elements in arr1 that are also in arr2 are arranged in the arr2 order first (4, 3, 2, 1), followed by the remaining elements of arr1 in ascending order (8, 8, 9).

Example 2:

• Input: arr1 = [5, 5, 4, 6, 4], arr2 = [4, 5]
• Expected Output: [4, 4, 5, 5, 6]
• Justification: First, we arrange the common elements in the order they appear in arr2 (4, 4, 5, 5), then append the remaining elements of arr1 sorted (6).

Example 3:

• Input: arr1 = [10, 20, 30, 20, 15, 20, 10], arr2 = [20, 10]
• Expected Output: [20, 20, 20, 10, 10, 15, 30]
• Justification: We follow the order in arr2 for common elements (20, 20, 20, 10, 10), then sort the rest (15, 30).

Solution

To solve this problem, we'll employ a custom sorting strategy that prioritizes the sequence specified in arr2 for the elements found in both arrays. This approach works because it allows us to maintain the relative order of arr2 in arr1 while ensuring that elements not present in arr2 are sorted in ascending order at the end of arr1. This method is efficient and straightforward because it directly addresses the problem's requirements by treating it as a two-part task: first, reordering according to arr2, and second, sorting the remaining elements.

In the initial phase, we'll map the elements of arr2 with their corresponding indices to efficiently check the order of elements that appear in arr1. For elements not in arr2, a separate list will be maintained and sorted later. This segregation ensures that we can easily append the sorted list of non-arr2 elements to the reordered list of arr1 elements. This strategy is effective because it minimizes the need for complex sorting logic, relying instead on the inherent order of arr2 and standard sorting for the remaining elements.

Step-by-step Algorithm

1. Initialize a HashMap (orderMap) to map each element in arr2 to its index. This will help us quickly identify the order of arr2 elements in arr1.

2. Create two Lists (arr2OrderList and nonArr2List):

   • arr2OrderList to hold elements found in both arr1 and arr2, to maintain the order specified by arr2.
   • nonArr2List to hold elements that are in arr1 but not in arr2, which will be sorted in ascending order later.

3. Iterate through arr1:

   • For each element, check if it exists in orderMap (meaning it's also in arr2).
     • If yes, add it to arr2OrderList.
     • If no, add it to nonArr2List.

4. Sort nonArr2List in ascending order since these elements do not have a specified order from arr2.

5. Sort arr2OrderList based on the indices stored in orderMap to maintain the order specified by arr2.

6. Merge the two lists: First, add all elements from arr2OrderList to the final result array, then append all elements from nonArr2List.

7. Return the merged array as the final sorted array.

Algorithm Walkthrough

Let's consider the Input:

• arr1 = [10, 20, 30, 20, 15, 20, 10]
• arr2 = [20, 10]

Step-by-Step Walkthrough:

1. Initialize orderMap:

   • orderMap = {20: 0, 10: 1}

2. Create Lists:

   • arr2OrderList = []
   • nonArr2List = []

3. Iterate through arr1:

   • For each element in arr1, check if it exists in orderMap:
     • 10 is in arr2, add to arr2OrderList → arr2OrderList = [10]
     • 20 is in arr2, add to arr2OrderList → arr2OrderList = [10, 20]
     • 30 is not in arr2, add to nonArr2List → nonArr2List = [30]
     • Another 20, add to arr2OrderList → arr2OrderList = [10, 20, 20]
     • 15 is not in arr2, add to nonArr2List → nonArr2List = [30, 15]
     • Another 20, add to arr2OrderList → arr2OrderList = [10, 20, 20, 20]
     • Another 10, add to arr2OrderList → arr2OrderList = [10, 20, 20, 20, 10]
   • After completing the iteration:
     • arr2OrderList contains [10, 20, 20, 20, 10]
     • nonArr2List contains [30, 15]

4. Sort nonArr2List in ascending order:

   • After sorting, nonArr2List becomes [15, 30].

5. Sort arr2OrderList based on the order in arr2:

   • To sort arr2OrderList based on arr2's order, we arrange the elements according to their index in orderMap. Since 20 has a lower index (0) than 10 (1), 20 should come before 10.
   • After sorting based on arr2's order, arr2OrderList should be rearranged to [20, 20, 20, 10, 10].

6. Merge arr2OrderList and nonArr2List for the final result:

   • Merge the sorted arr2OrderList with the sorted nonArr2List.
   • The final result array after merging: [20, 20, 20, 10, 10, 15, 30].

7. Return the final sorted array.

Code

import java.util.*;

public class Solution {

  public int[] relativeSortArray(int[] arr1, int[] arr2) {
    // Map to store the index of each element in arr2 for quick lookup
    Map<Integer, Integer> orderMap = new HashMap<>();
    for (int i = 0; i < arr2.length; i++) {
      orderMap.put(arr2[i], i);
    }

    // List to hold elements of arr1 not in arr2
    List<Integer> nonArr2List = new ArrayList<>();
    // List to hold elements of arr1 in the order specified by arr2
    List<Integer> arr2OrderList = new ArrayList<>();

    for (int value : arr1) {
      if (orderMap.containsKey(value)) {
        // If the element is in arr2, add it to arr2OrderList for later sorting
        arr2OrderList.add(value);
      } else {
        // If not, add it to nonArr2List to be sorted independently
        nonArr2List.add(value);
      }
    }

    // Sort nonArr2List in natural order
    Collections.sort(nonArr2List);
    // Sort arr2OrderList based on the order in arr2 using the orderMap
    arr2OrderList.sort(Comparator.comparingInt(orderMap::get));

    // Prepare the result array
    int[] result = new int[arr1.length];
    int index = 0;
    // Add elements from arr2OrderList first
    for (int num : arr2OrderList) {
      result[index++] = num;
    }
    // Then add sorted elements from nonArr2List
    for (int num : nonArr2List) {
      result[index++] = num;
    }

    return result;
  }

  public static void main(String[] args) {
    Solution solution = new Solution();
    // Test with example inputs
    System.out.println(
      Arrays.toString(
        solution.relativeSortArray(
          new int[] { 8, 1, 2, 3, 4, 8, 9 },
          new int[] { 4, 3, 2, 1 }
        )
      )
    );
    System.out.println(
      Arrays.toString(
        solution.relativeSortArray(
          new int[] { 5, 5, 4, 6, 4 },
          new int[] { 4, 5 }
        )
      )
    );
    System.out.println(
      Arrays.toString(
        solution.relativeSortArray(
          new int[] { 10, 20, 30, 20, 15, 20, 10 },
          new int[] { 20, 10 }
        )
      )
    );
  }
}

Complexity Analysis

• Time Complexity: The time complexity of this algorithm is , where N is the number of elements in arr1. This is because we sort the elements of arr1 that are not found in arr2. The mapping and iteration steps are linear in complexity.
• Space Complexity: The space complexity is , as we store the elements of arr1 in separate lists or arrays before combining them into the final result array.