Leetcode 1122: Relative Sort Array
You are given two arrays:
arr1 and arr2. The elements of arr2 are distinct, and all elements in arr2 exist in arr1. The task is to sort the elements of arr1 such that the relative ordering of elements in arr1 matches the order of elements in arr2. Elements in arr1 that are not present in arr2 should be placed at the end of arr1 in ascending order.Problem
Approach
Steps
Complexity
Input: The input consists of two integer arrays, `arr1` and `arr2`. The length of `arr1` and `arr2` can range from 1 to 1000, and all elements in `arr2` are distinct and exist in `arr1`.
Example: Input: arr1 = [5, 6, 1, 3, 9, 1, 7], arr2 = [3, 1, 7]
Constraints:
• 1 <= arr1.length, arr2.length <= 1000
• 0 <= arr1[i], arr2[i] <= 1000
• All elements of arr2 are distinct.
• Each element of arr2 is present in arr1.
Output: The output should be an array where the elements in `arr1` are sorted such that the relative order of elements from `arr2` is preserved, and elements not in `arr2` appear at the end of the array in ascending order.
Example: Output: [3, 1, 7, 5, 6, 9]
Constraints:
• The elements in arr1 should be sorted in the specified order as per arr2.
Goal: Sort the elements of `arr1` based on their position in `arr2`, and place the remaining elements at the end in ascending order.
Steps:
• Create a mapping for the elements in `arr2` to track their order.
• Sort the elements of `arr1` by using this mapping to prioritize the order of `arr2` elements.
• For elements not in `arr2`, sort them in ascending order and append them at the end of the array.
Goal: Ensure that the elements of `arr1` are reordered such that those in `arr2` appear first in the order given, followed by the remaining elements sorted in ascending order.
Steps:
• The algorithm must preserve the relative order of `arr1` as defined by `arr2`.
Assumptions:
• Each element of `arr2` exists at least once in `arr1`.
• Elements of `arr1` that are not present in `arr2` should be sorted and placed at the end.
• Input: Input: arr1 = [4, 3, 1, 2], arr2 = [3, 1]
• Explanation: In this case, the output should be `[3, 1, 2, 4]` because the order of elements in `arr1` matching `arr2` (3 first, then 1) is preserved, and the remaining elements (2, 4) are placed at the end in ascending order.
• Input: Input: arr1 = [10, 5, 7, 6], arr2 = [5, 6]
• Explanation: The output should be `[5, 6, 7, 10]` as `arr1` elements in `arr2` (5, 6) are placed first, and the remaining elements (7, 10) are sorted and placed at the end.
Approach: The approach is to first create a mapping of the order of elements in `arr2`, then sort `arr1` such that elements in `arr2` come first. Elements in `arr1` that are not in `arr2` will be sorted and appended at the end.
Observations:
• The order of elements in `arr1` should respect the order specified in `arr2`.
• By creating a mapping for `arr2`, we can sort `arr1` accordingly and handle the remaining elements by sorting them in ascending order.
Steps:
• Create a dictionary to map the index of each element in `arr2`.
• Sort `arr1` by using this dictionary to determine the relative order of the elements.
• Sort the remaining elements (those not in `arr2`) in ascending order and append them at the end.
Empty Inputs:
• If either `arr1` or `arr2` is empty, return an empty array.
Large Inputs:
• The solution should efficiently handle arrays of size up to 1000.
Special Values:
• If all elements in `arr1` are already in `arr2`, the output should be exactly the same as `arr2`.
Constraints:
• The solution must ensure that sorting is done in linear time for the elements that are in `arr2`, and the remaining elements are sorted in ascending order.
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
int n1=arr1.size(), n2=arr2.size();
int a2i[1001];
fill(a2i, end(a2i), n2);
for(int i=0; i<n2; i++)
a2i[arr2[i]]=i;
sort(arr1.begin(), arr1.end(), [&](int x, int y){
if (a2i[x]==a2i[y]) return x<y;
return a2i[x]<a2i[y];
});
return arr1;
}
1 : Function Declaration
vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
Declares the function `relativeSortArray` that takes two input arrays, `arr1` and `arr2`, and returns a sorted `arr1` based on the order defined by `arr2`.
2 : Variable Initialization
int n1=arr1.size(), n2=arr2.size();
Initializes variables `n1` and `n2` to store the sizes of `arr1` and `arr2` respectively.
3 : Array Declaration
int a2i[1001];
Declares an integer array `a2i` with 1001 elements, which will be used to map the values in `arr2` to their respective indices.
4 : Initialization
This section is left empty to highlight initialization steps done later in the code.
5 : Array Initialization
fill(a2i, end(a2i), n2);
Fills the entire `a2i` array with the value `n2` (the size of `arr2`), which ensures that elements not present in `arr2` will be considered as the largest value during sorting.
6 : Loop
for(int i=0; i<n2; i++)
Begins a loop over `arr2` to populate the `a2i` array with the correct indices for each element in `arr2`.
7 : Array Mapping
a2i[arr2[i]]=i;
Maps each element `arr2[i]` to its index `i` in the `a2i` array. This will help to sort the elements of `arr1` based on their index in `arr2`.
8 : Sorting Function
This section is left empty to emphasize the use of sorting functions to arrange the elements of `arr1`.
9 : Sorting Logic
sort(arr1.begin(), arr1.end(), [&](int x, int y){
Begins the sorting of `arr1` using a custom comparator function that compares elements based on their positions in `arr2`.
10 : Comparison Logic
if (a2i[x]==a2i[y]) return x<y;
If two elements `x` and `y` from `arr1` have the same index in `arr2`, they are compared using their natural order (`x < y`).
11 : Comparison Logic
return a2i[x]<a2i[y];
If two elements `x` and `y` from `arr1` have different indices in `arr2`, they are compared based on the order defined by their indices in `arr2`.
12 : End Sorting
});
Ends the custom sorting function, applying the comparator to the entire `arr1`.
13 : Return Statement
return arr1;
Returns the sorted `arr1` array, which is now ordered according to the positions of its elements in `arr2` and any remaining elements sorted in ascending order.
14 : Function End
}
Marks the end of the `relativeSortArray` function.
Best Case: O(n log n)
Average Case: O(n log n)
Worst Case: O(n log n)
Description: The time complexity is dominated by the sorting operations. Sorting `arr1` based on the order from `arr2` takes O(n log n), where `n` is the size of `arr1`.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the extra space used for storing the mapping of `arr2` and sorting elements.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus