_1122. Relative Sort Array.md

1122. Relative Sort Array

Back to top

---

First completed : June 10, 2024

Last updated : July 01, 2024

---

Related Topics : Array, Hash Table, Sorting, Counting Sort

Acceptance Rate : 74.663 %

---

To see the question prompt, click the title.

Solutions

• e1122 Daily.py
• e1122.java

Python

e1122 Daily.py

class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        cnt = Counter(arr1)
        arr2Set = set(arr2)
        output = []

        for i in arr2 :
            output.extend([i] * cnt.get(i))
            cnt.pop(i)
        
        for key in sorted(cnt.keys()) :
            output.extend([key] * cnt.get(key))

        return output

Java

e1122.java

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        HashSet<Integer> arr2vals = new HashSet<>();
        for (Integer i : arr2) {
            arr2vals.add(i);
        }

        HashMap<Integer, Integer> cnt = new HashMap<>();
        for (Integer i : arr1) {
            cnt.put(i, cnt.getOrDefault(i, 0) + 1);
        }


        int indx = 0;
        int[] output = new int[arr1.length];
        for (int i : arr2) {
            for (int j = 0; j < cnt.get(i); j++, indx++) {
                output[indx] = i;
            }
            cnt.remove(i);
        }
        
        int remainderIndx = 0;
        int[] remainingKeys = new int[cnt.size()];
        for (Integer i : cnt.keySet()) {
            remainingKeys[remainderIndx] = i;
            remainderIndx++;
        }
        Arrays.sort(remainingKeys);

        for (Integer i : remainingKeys) {
            for (int j = 0; j < cnt.get(i); j++, indx++) {
                output[indx] = i;
            }
        }

        return output;

    }
}