algoadvance

Leetcode 1122. Relative Sort Array

Problem Statement

You are given two arrays arr1 and arr2, where:

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.

Example:

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]

Constraints:

Clarifying Questions

  1. Are there any negative numbers in the arrays?
    • No, the problem constraints indicate that numbers range from 0 to 1000.
  2. Can the arrays have repeated numbers?
    • Yes, arr1 can have repeated numbers but arr2 contains unique elements.
  3. How should numbers that do not appear in arr2 be sorted?
    • They should be sorted in ascending order and placed at the end of arr1.

Strategy

  1. Create a frequency map for elements in arr1.
  2. Generate the result list by adding elements in arr2 order and then adding the rest in ascending order.
  3. Iterate through arr1 and use the frequency map to build the final array.
  4. Time Complexity:
    • Building the frequency map: O(n) where n is the length of arr1.
    • Iterating and placing elements according to arr2: O(m) where m is the length of arr2.
    • Sorting remaining elements: O(k log k) where k is the number of elements not in arr2.
    • Combining these, the overall time complexity is O(n + k log k).

Code

import java.util.*;

public class RelativeSortArray {
    public static int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] result = new int[arr1.length];
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        
        // Fill the frequency map for arr1
        for (int num : arr1) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        int index = 0;

        // Add elements of arr2 in the order they appear in arr2
        for (int num : arr2) {
            if (frequencyMap.containsKey(num)) {
                int count = frequencyMap.get(num);
                for (int i = 0; i < count; i++) {
                    result[index++] = num;
                }
                frequencyMap.remove(num);
            }
        }

        // Get remaining elements and sort them
        List<Integer> remainingElements = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            int num = entry.getKey();
            int count = entry.getValue();
            for (int i = 0; i < count; i++) {
                remainingElements.add(num);
            }
        }
        Collections.sort(remainingElements);
        
        // Add remaining sorted elements to result
        for (int num : remainingElements) {
            result[index++] = num;
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr1 = {2,3,1,3,2,4,6,7,9,2,19};
        int[] arr2 = {2,1,4,3,9,6};
        System.out.println(Arrays.toString(relativeSortArray(arr1, arr2)));
    }
}

Time Complexity

This solution is efficient and adheres to the constraints provided.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI