To solve this problem, map the values of arr2 using a hashmap to preserve their order in arr1. Then, move any elements of arr1 that are not in arr2 to the end and sort them. This approach leverages array scanning and hash lookups to ensure efficiency and correctness.
Problem Statement
Given two arrays, arr1 and arr2, where all elements of arr2 are distinct and also present in arr1, the task is to reorder arr1 based on the order of elements in arr2. The relative ordering of elements in arr1 should match the order of arr2, and the elements of arr1 that are not in arr2 should be placed at the end, in ascending order.
For example, if arr1 = [2,3,1,3,2,4,6,7,9,2,19] and arr2 = [2,1,4,3,9,6], the correct output is [2,2,2,1,4,3,3,9,6,7,19]. The elements of arr1 are reordered such that the elements appearing in arr2 appear first, preserving their relative order, and any remaining elements from arr1 are sorted in ascending order.
Examples
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 details omitted.
Example 2
Input: arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
Output: [22,28,8,6,17,44]
Example details omitted.
Constraints
- 1 <= arr1.length, arr2.length <= 1000
- 0 <= arr1[i], arr2[i] <= 1000
- All the elements of arr2 are distinct.
- Each arr2[i] is in arr1.
Solution Approach
Hashmap for Ordering
Use a hashmap to map each element in arr2 to its index. This allows us to maintain the relative order of the elements from arr2 when rearranging arr1.
Array Scanning and Sorting
Traverse arr1, and for each element that exists in arr2, place it in its respective position in the output array. Afterward, elements not in arr2 are sorted and added to the end.
Final Merging
Once the elements from arr2 are positioned correctly in arr1, append the remaining elements that don't appear in arr2, and sort them in ascending order before adding them to the result.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(n + m + k) |
| Space | O(k) |
The time complexity is O(n + m + k), where n is the length of arr1, m is the length of arr2, and k is the number of elements not in arr2. The space complexity is O(k) due to the storage of remaining elements in arr1 that aren't in arr2 and need to be sorted.
What Interviewers Usually Probe
- Look for an efficient implementation that minimizes unnecessary sorting.
- Test the candidate's ability to use a hashmap for ordering and scanning.
- Check how the candidate handles edge cases, such as when arr1 and arr2 are the same length.
Common Pitfalls or Variants
Common pitfalls
- Failing to account for elements in arr1 that aren't in arr2, leading to incorrect output.
- Not maintaining the relative order of elements in arr1 that match arr2.
- Not sorting the leftover elements of arr1 correctly at the end.
Follow-up variants
- Handling cases where arr1 and arr2 contain repeated elements.
- Optimizing space usage if constraints change, such as limiting space complexity to O(1).
- Implementing a version that sorts arr1 directly without using a hashmap.
How GhostInterview Helps
- GhostInterview helps by focusing on the key pattern of array scanning and hashmap lookups, ensuring efficient solutions.
- GhostInterview assists in debugging common mistakes, such as misplacing or misordering elements that aren't in arr2.
- GhostInterview's explanations guide you through the complexity analysis, making sure you understand both time and space constraints.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
How does the relative ordering of elements work in the 'Relative Sort Array' problem?
The relative ordering of elements in arr1 must match the order of elements in arr2. Elements not in arr2 are placed at the end, in ascending order.
What is the main pattern used in the 'Relative Sort Array' problem?
The main pattern is array scanning combined with hash lookup. A hashmap is used to track the order of elements from arr2, and scanning arr1 ensures elements are placed correctly.
How do we handle elements in arr1 that aren't in arr2?
Elements in arr1 that aren't in arr2 should be placed at the end and sorted in ascending order before appending them to the result.
What is the time complexity of the 'Relative Sort Array' problem?
The time complexity is O(n + m + k), where n is the length of arr1, m is the length of arr2, and k is the number of elements not in arr2.
How does GhostInterview help with the 'Relative Sort Array' problem?
GhostInterview helps by providing a clear breakdown of the solution approach and common pitfalls, assisting you in writing optimized code and debugging efficiently.
Need direct help with Relative Sort Array instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Relative Sort Array from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
In this problem, you need to determine how many numbers are smaller than each element in an array, focusing on array scanning and hash lookup.
Open problem page#1090 Largest Values From LabelsMaximize the sum of selected item values while respecting label use limits using array scanning and hash tracking.
Open problem page#1169 Invalid TransactionsDetect invalid transactions by scanning arrays and cross-checking with hash tables for time, amount, and city conflicts efficiently.
Open problem page