1122. Relative Sort Array

there is a constrait : 0 <= arr1[i], arr2[i] <= 1000 .=> so we can use idea like couting sort

time: O(m+n)

space: O(1), in-place

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

use treemap

follow-up:

What if this constraint 0 <= arr1[i], arr2[i] <= 1000 doesn't exist?

time: O(nLogn)

space: O(n)

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int n : arr1) {
            map.put(n, map.getOrDefault(n, 0) + 1);
        }
        int i = 0;
        for (int n : arr2) {
            for (int j = 0; j < map.get(n); j++) {
                arr1[i++] = n;
            }
            map.remove(n);
        }
        for (int n : map.keySet()) {
            for (int j = 0; j < map.get(n); j++) {
                arr1[i++] = n;
            }
        }
        return arr1;
    }
}

my origin idea:

time: O(nLogn)

space: O(n)

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        // brute force iterate arr2 , each arr2 element will scan arr1 once, so O(n*m)
        
        // put arr2 to hash table, build key with empty list
        // iterate arr1, put value into key arraylist, can't get the key, put into others arraylist
        // finally, iterate arr2 again, bring the correspond arraylist from hash table
        List<Integer> res = new ArrayList<>();

        Map<Integer, ArrayList<Integer>> map = new HashMap<>();
        for (int ar2 : arr2) {
            map.put(ar2, new ArrayList<>());
        }
        List<Integer> others = new ArrayList<>();
        for (int ar1 : arr1) {
            if (map.containsKey(ar1)) {
                List<Integer> list = map.get(ar1);
                list.add(ar1);
            } else {
                others.add(ar1);
            }
        }
        Collections.sort(others);
        for (int ar2 : arr2) {
            List<Integer> result = map.get(ar2);
            res.addAll(result);
        }
        res.addAll(others);
        return res.stream().mapToInt(i -> i).toArray();
    }
}