algoadvance

Leetcode 1122. Relative Sort Array

Problem Statement

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 so 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 1:

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:

Input: arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
Output: [22,28,8,6,17,44]

Clarifying Questions

  1. Are there any constraints on the array lengths?
    • There is no specific constraint provided. Assume typical constraints.
  2. Is it safe to assume all elements of arr2 are in arr1?
    • Yes, as stated in the problem.
  3. What should be done with elements in arr1 that are not in arr2?
    • They should be placed at the end in ascending order.
  4. Do we need to consider duplicate numbers in arr1?
    • Yes, duplicates in arr1 should be handled accordingly.

Strategy

  1. Count Elements: First, count the occurrences of each element in arr1.
  2. Sort by arr2: Use arr2 to determine the initial order of elements, respecting their counts.
  3. Sort Remaining Elements: Sort and append the remaining elements of arr1 that are not in arr2.

Code

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

std::vector<int> relativeSortArray(std::vector<int>& arr1, std::vector<int>& arr2) {
    std::unordered_map<int, int> countMap;
    for (int num : arr1) {
        countMap[num]++;
    }

    std::vector<int> result;

    // Adding elements from arr2 in the required order
    for (int num : arr2) {
        while (countMap[num] > 0) {
            result.push_back(num);
            countMap[num]--;
        }
    }
    
    // Adding remaining elements from arr1 not in arr2
    std::vector<int> remainingElements;
    for (const auto& entry : countMap) {
        while (entry.second > 0) {
            remainingElements.push_back(entry.first);
            entry.second--;
        }
    }
    std::sort(remainingElements.begin(), remainingElements.end());

    // Merge results
    result.insert(result.end(), remainingElements.begin(), remainingElements.end());

    return result;
}

int main() {
    std::vector<int> arr1 = {2,3,1,3,2,4,6,7,9,2,19};
    std::vector<int> arr2 = {2,1,4,3,9,6};
    std::vector<int> result = relativeSortArray(arr1, arr2);
    
    for(int num : result) {
        std::cout << num << " ";
    }
    
    return 0;
}

Time Complexity

  1. Counting Elements: O(N) where N is the size of arr1.
  2. Sorting Remaining Elements: O(M log M) where M is the number of elements not in arr2.
  3. Overall: O(N + M log M) which simplifies to O(N log N) in the worst case, where N is the length of arr1.

This approach ensures that the algorithm runs efficiently and meets the problem requirements.

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