What is the time complexity of Relative Sort Array?

The optimal solution has a time complexity of O(n + m + klogk).

What data structures are used to solve Relative Sort Array?

This problem uses Array, Hash Table, Sorting, Counting Sort. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Relative Sort Array?

**Pre-Counting for Inventory Management:** The initial pass through `arr1` to create a frequency map (`counts` dictionary) is crucial. This step effectively takes an inventory of all numbers and their exact quantities, allowing us to reconstruct the array piece by piece without losing any elements or their original multiplicity. It's the foundation for accurate reconstruction. **Strategic Two-Phase Population:** The problem naturally breaks down into two distinct groups of numbers: those whose positions are dictated by `arr2`, and those that are 'leftovers'. By first iterating through `arr2` and using the frequency map to populate the `result` list, we directly implement the primary sorting rule. Crucially, removing processed elements from the `counts` map then leaves *only* the 'leftover' numbers, making their identification clean and efficient.

Which companies ask LeetCode 1122. Relative Sort Array in interviews?

This problem is frequently asked at DE Shaw.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Relative Sort Array - LeetCode 1122 Solution

Relative Sort Array - Complete Solution Guide

Relative Sort Array is LeetCode problem 1122, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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 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 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] C

Detailed Explanation

This problem asks us to reorder `arr1` according to a very specific set of rules defined by `arr2`. The primary directive is that any numbers from `arr1` that also appear in `arr2` must maintain their *relative order* as seen in `arr2`. For instance, if `arr2` is `[X, Y, Z]`, then all occurrences of `X` from `arr1` must come before all occurrences of `Y`, which in turn must come before all occurrences of `Z`. Importantly, we must preserve the original counts of each number from `arr1`. If `2` appears three times in `arr1` and `2` is in `arr2`, all three `2`s must be in the final output, grouped together in `arr2`'s specified position.

Solution Approach

The elegant solution provided hinges on a two-phase construction process, enabled by a frequency map. First, we iterate through `arr1` to build a `counts` dictionary, meticulously recording how many times each number appears. This is our complete inventory of numbers and their quantities. In the first phase of construction, we iterate through `arr2`. For each number `num` in `arr2`, we check our `counts` dictionary. We then append `num` to our `result` list `counts[num]` times. After placing all instances of `num`, we remove `num` from `counts` to mark it as processed. This step guarantees that the `arr2`-specified ordering is strictly adhered to, and all required numbers are placed.

Step-by-Step Algorithm

Count the occurrences of each element in `arr1` using a hash table or an array (counting sort).
Iterate through `arr2`. For each element, add it to the result array as many times as its count in `arr1`. Update its count after each addition.
Iterate through all possible elements (from 0 up to the maximum value in `arr1`). Add any remaining elements (those not in `arr2` but present in `arr1`) to the result array, ensuring they are added in ascending order.
Return the result array.

Key Insights

**Pre-Counting for Inventory Management:** The initial pass through `arr1` to create a frequency map (`counts` dictionary) is crucial. This step effectively takes an inventory of all numbers and their exact quantities, allowing us to reconstruct the array piece by piece without losing any elements or their original multiplicity. It's the foundation for accurate reconstruction.
**Strategic Two-Phase Population:** The problem naturally breaks down into two distinct groups of numbers: those whose positions are dictated by `arr2`, and those that are 'leftovers'. By first iterating through `arr2` and using the frequency map to populate the `result` list, we directly implement the primary sorting rule. Crucially, removing processed elements from the `counts` map then leaves *only* the 'leftover' numbers, making their identification clean and efficient.
**Efficient Outlier Handling:** After the `arr2`-defined elements are placed, any remaining entries in the `counts` map represent numbers from `arr1` that did not appear in `arr2`. These 'outliers' are gathered into a `remaining` list. The final step is simply to sort this `remaining` list in ascending order and append it to the already constructed `result`. This modular approach simplifies the sorting logic, as only the outliers need a standard sort.

Complexity Analysis

Time Complexity: O(n + m + klogk)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, Sorting, Counting Sort.

Companies

Asked at: DE Shaw.

Relative Sort Array | LeetCode 1122

Easy

Array Hash Table Sorting Counting Sort

Time: O(n + m + klogk)Space: O(n)

Solution Code

Available in:

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] count = new int[1001];
        for (int num : arr1) {
            count[num]++;
        }

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

        for (int num : arr2) {
            while (count[num] > 0) {
                result[index++] = num;
                count[num]--;
            }
        }

        for (int i = 0; i < 1001; i++) {
            while (count[i] > 0) {
                result[index++] = i;
                count[i]--;
            }
        }

        return result;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1122: Relative Sort Array - Detailed explanation and solution approaches.

Topics

Array Hash Table Sorting Counting Sort

Companies

DE Shaw

Stats

Difficulty:Easy

Languages:4

Companies:1

Problem #:1122

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

4 steps

1
Count the occurrences of each element in `arr1` using a hash table or an array (counting sort).
2
Iterate through `arr2`. For each element, add it to the result array as many times as its count in `arr1`. Update its count after each addition.
3
Iterate through all possible elements (from 0 up to the maximum value in `arr1`). Add any remaining elements (those not in `arr2` but present in `arr1`) to the result array, ensuring they are added in ascending order.
4
Return the result array.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n + m + klogk)

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

where n is the length of `arr1`, m is the length of `arr2`, and k is the range of numbers (1001 in this case). Counting the elements in `arr1` takes O(n) time. Iterating through `arr2` to add elements based on counts is O(m). Finally, sorting and adding the remaining elements takes O(k log k) in the worst case, as we might need to sort almost all of the possible values. The space complexity is O(k) due to the counting array/hash table that stores element frequencies.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using `std::sort` with a custom comparator (C++)

Sort `arr1` using `std::sort` with a comparator that prioritizes elements present in `arr2` according to their order in `arr2`. Elements not in `arr2` are placed at the end.

Time: O(n log n)Space: O(1)

Trade-offs: This approach has a slightly worse time complexity (O(n log n)) compared to the counting sort approach (O(n + m + k log k)). However, it is simpler to implement and might be preferable if the range of values k is very large.

✨

Key Insights

1**Pre-Counting for Inventory Management:** The initial pass through `arr1` to create a frequency map (`counts` dictionary) is crucial. This step effectively takes an inventory of all numbers and their exact quantities, allowing us to reconstruct the array piece by piece without losing any elements or their original multiplicity. It's the foundation for accurate reconstruction.
2**Strategic Two-Phase Population:** The problem naturally breaks down into two distinct groups of numbers: those whose positions are dictated by `arr2`, and those that are 'leftovers'. By first iterating through `arr2` and using the frequency map to populate the `result` list, we directly implement the primary sorting rule. Crucially, removing processed elements from the `counts` map then leaves *only* the 'leftover' numbers, making their identification clean and efficient.
3**Efficient Outlier Handling:** After the `arr2`-defined elements are placed, any remaining entries in the `counts` map represent numbers from `arr1` that did not appear in `arr2`. These 'outliers' are gathered into a `remaining` list. The final step is simply to sort this `remaining` list in ascending order and append it to the already constructed `result`. This modular approach simplifies the sorting logic, as only the outliers need a standard sort.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Sorting

Arranging elements in a specific order (ascending/descending).

Edge Cases

Empty `arr1` or `arr2`: The solutions handle empty arrays gracefully. The result will be an empty array if `arr1` is empty.
All elements of `arr1` are present in `arr2`: In this case, the `remaining` array (or the second loop in the counting sort based solution) will be empty, and only the elements from `arr2` will be present in the output, maintaining their relative order.

⚠️

Common Mistakes to Avoid

✗Forgetting to sort the remaining elements: After processing elements from `arr2`, it's crucial to sort the remaining elements in ascending order before appending them to the result.

✗Incorrectly handling duplicate elements: The solution must account for the possibility of duplicate elements in `arr1`. The counting array/hashmap is critical for this.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Customizable sorting of data based on priority: Imagine sorting a list of products based on customer ratings, where specific products are prioritized based on a promotional campaign.

🏦Log file processing: Sorting log entries based on a specific field (e.g., timestamps) while keeping the order of those fields, and then adding unsorted entries.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Even for easy problems, discuss time and space complexity. Interviewers want to see you think analytically.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 13, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 14

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 7

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What are the trade-offs of using a hash table?

Hash tables provide O(1) average-case lookup, insertion, and deletion, making them ideal for frequency counting and duplicate detection. However, they use O(n) extra space and may degrade to O(n) time in worst-case scenarios with hash collisions. Always consider if the space trade-off is acceptable.

How should I approach easy-level algorithm problems?

Easy problems build foundational skills. Focus on: 1) Understanding the problem completely before coding, 2) Writing clean, readable code, 3) Handling all edge cases (empty input, single element, etc.), 4) Analyzing time and space complexity. Don't skip complexity analysis even for simple solutions.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Relative Sort Array"?

For this easy-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?