LeetCode 1122: Relative Sort Array Solution

Master LeetCode problem 1122 (Relative Sort Array), a easy challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1122. Relative Sort Array

Easy

Array Hash Table Sorting Counting Sort

Problem Explanation

Explanation

To solve this problem, we can use a hashmap to store the frequency of each element in arr1. Then, we iterate over arr2 and add the elements in the correct order based on their frequency in arr1. Finally, we add the remaining elements from arr1 that are not present in arr2 in ascending order.

Time Complexity: O(nlogn) where n is the length of arr1.
Space Complexity: O(n) where n is the length of arr1.

Solution Code

import java.util.*;

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : arr1) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        int[] result = new int[arr1.length];
        int index = 0;

        for (int num : arr2) {
            int freq = freqMap.get(num);
            for (int i = 0; i < freq; i++) {
                result[index++] = num;
            }
            freqMap.remove(num);
        }

        List<Integer> remaining = new ArrayList<>();
        for (int num : freqMap.keySet()) {
            remaining.addAll(Collections.nCopies(freqMap.get(num), num));
        }

        Collections.sort(remaining);

        for (int num : remaining) {
            result[index++] = num;
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1122 (Relative Sort Array)?

This page provides optimized solutions for LeetCode problem 1122 (Relative Sort Array) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1122 (Relative Sort Array)?

The time complexity for LeetCode 1122 (Relative Sort Array) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1122 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1122 in Java, C++, or Python.

Back to LeetCode Solutions