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.

Examples

Example 1:

1
2

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:

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

Solution

We can either use map + sorting, or TreeMap OR map + heap or bucket to sort this problem. Here is the video explanation:

Method 1 - Using Map and Sorting

  1. We can use counts as frequency map on arr1.
  2. Then, we loop on arr2, and if key is present in counts, we append to the present list for value number of times
  3. Then, we check arr2 and counts map to find the keys that don’t exist in arr2 and append them value number of times to notPresent list
  4. Then, we sort notPresent list
  5. Finally, we append notPresent list to present list and that is our answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Long> counts = Arrays.stream(arr1).boxed().collect(
                Collectors.groupingBy(
                        Function.identity(),
                        HashMap::new, // can be skipped
                        Collectors.counting()
                )
        );

        Set<Integer> set = Arrays.stream(arr2).boxed().collect(Collectors.toSet());

        List<Integer> present = new ArrayList<>();
        for (int num : arr2) {
            long count = counts.get(num);
            for (int i = 0; i < count; i++) {
                present.add(num);
            }
        }

        List<Integer> notPresent = new ArrayList<>();
        for (int k : counts.keySet()) {
            if (!set.contains(k)) {
                long count = counts.get(k);
                for (int i = 0; i < count; i++) {
                    notPresent.add(k);
                }
            }
        }
        notPresent.sort(Comparator.comparingInt(o -> o));

        int n = present.size();
        int m = notPresent.size();

        int[] ans = new int[present.size() + notPresent.size()];

        IntStream.range(0, n).forEach(i -> {
            ans[i] = present.get(i);
        });

        IntStream.range(0, m).forEach(i -> {
            ans[i + n] = notPresent.get(i);
        });
        
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n)

Method 2 - Using Bucketsort with array

  1. Because 0 <= arr1[i], arr2[i] <= 1000, we use an array to count every element, lets call it cnt.
  2. Now, we don’t need arr1, we can actually fill the sorted array in place. So, we will go through arr2, from left to right. When, we find frequency of it in cnt, we fill it in arr1.
  3. Now, we fill in remaining elements in cnt, which are not yet encountered.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] cnt = new int[1001];
        for(int num : arr1) {
	        cnt[num]++;
	    }
        int i = 0;
        for(int num : arr2) {
            while(cnt[num]-- > 0) {
                arr1[i++] = num;
            }
        }
        for(int num = 0; num < cnt.length; num++) {
            while(cnt[num]-- > 0) {
                arr1[i++] = num;
            }
        }
        return arr1;
    }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n) for using the count array