What is the time complexity of Find Original Array From Doubled Array?

The optimal solution has a time complexity of O(n log n).

What data structures are used to solve Find Original Array From Doubled Array?

This problem uses Array, Hash Table, Greedy, Sorting. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Find Original Array From Doubled Array?

Insight 1: The length of the `changed` array must be even for it to be a doubled array because each element in `original` contributes two elements to `changed` (itself and its double). Insight 2: Sorting the `changed` array simplifies the search for doubled elements. By iterating through the sorted array, we can efficiently check if the doubled value exists and remove both from consideration using a counter.

Which companies ask LeetCode 2007. Find Original Array From Doubled Array in interviews?

This problem is frequently asked at Accenture, Verily.

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

Find Original Array From Doubled Array - LeetCode 2007 Solution

Find Original Array From Doubled Array - Complete Solution Guide

Find Original Array From Doubled Array is LeetCode problem 2007, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

An integer array original is transformed into a doubled array changed by appending twice the value of every element in original , and then randomly shuffling the resulting array. Given an array changed , return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order . Example 1: Input: changed = [1,3,4,2,6,8] Output: [1,3,4] Explanation: One possible original array could be [1,3,4]: - Twice the value

Detailed Explanation

The problem asks us to determine if a given array `changed` is a doubled array, meaning it was created by taking an original array `original`, appending each element's double to it, and then shuffling the result. If `changed` is a doubled array, we should return the `original` array. If not, we should return an empty array. The order of elements in `original` doesn't matter. For example, if `changed = [1, 3, 4, 2, 6, 8]`, a possible `original` is `[1, 3, 4]` because 2*1=2, 2*3=6, and 2*4=8, and all these elements are present in `changed`.

Solution Approach

The provided solution first checks if the length of `changed` is even. If not, it returns an empty array. Then, it uses a hash table (Counter in Python, HashMap in Java/C++, custom HashTable in C) to count the occurrences of each number in `changed`. Next, it sorts the `changed` array. The solution then iterates through the sorted `changed` array. For each number, it checks if its count is greater than 0. If it is, the solution decrements the count of that number and checks if its double is also present with a count greater than 0. If the double exists, its count is also decremented, and the original number is added to the `original` array. If the double doesn't exist, it implies `changed` is not a doubled array, so an empty array is returned.

Step-by-Step Algorithm

Step 1: Check if the length of `changed` is even. If it's odd, return an empty array.
Step 2: Create a hash table (or counter) to store the frequency of each number in `changed`.
Step 3: Sort the `changed` array.
Step 4: Iterate through the sorted `changed` array.
Step 5: For each number, check if its count in the hash table is greater than 0.
Step 6: If the count is greater than 0, decrement the count. Calculate the double of the current number.
Step 7: Check if the double exists in the hash table and has a count greater than 0.
Step 8: If the double exists, decrement its count and add the original number to the `original` array.
Step 9: If the double doesn't exist, return an empty array.
Step 10: If the loop completes without returning an empty array, return the `original` array.

Key Insights

Insight 1: The length of the `changed` array must be even for it to be a doubled array because each element in `original` contributes two elements to `changed` (itself and its double).
Insight 2: Sorting the `changed` array simplifies the search for doubled elements. By iterating through the sorted array, we can efficiently check if the doubled value exists and remove both from consideration using a counter.
Insight 3: Using a hash table (or counter) to keep track of the frequency of each number allows for efficient checking and removal of elements.

Complexity Analysis

Time Complexity: O(n log n)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, Greedy, Sorting.

Companies

Asked at: Accenture, Verily.

Find Original Array From Doubled Array | LeetCode 2007

Medium

Array Hash Table Greedy Sorting

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

Solution Code

Available in:

import java.util.*;

class Solution {
    public int[] findOriginalArray(int[] changed) {
        int n = changed.length;
        if (n % 2 != 0) {
            return new int[0];
        }

        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : changed) {
            counts.put(num, counts.getOrDefault(num, 0) + 1);
        }

        Arrays.sort(changed);

        List<Integer> original = new ArrayList<>();
        for (int num : changed) {
            if (counts.get(num) == null || counts.get(num) == 0) {
                continue;
            }

            counts.put(num, counts.get(num) - 1);
            int double_num = num * 2;

            if (counts.containsKey(double_num) && counts.get(double_num) > 0) {
                original.add(num);
                counts.put(double_num, counts.get(double_num) - 1);
            } else {
                return new int[0];
            }
        }

        int[] result = new int[original.size()];
        for (int i = 0; i < original.size(); i++) {
            result[i] = original.get(i);
        }
        return result;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 2007: Find Original Array From Doubled Array - Detailed explanation and solution approaches.

Topics

Array Hash Table Greedy Sorting

Companies

AccentureVerily

Stats

Difficulty:Medium

Languages:4

Companies:2

Problem #:2007

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

10 steps

1
Step 1: Check if the length of `changed` is even. If it's odd, return an empty array.
2
Step 2: Create a hash table (or counter) to store the frequency of each number in `changed`.
3
Step 3: Sort the `changed` array.
4
Step 4: Iterate through the sorted `changed` array.
5
Step 5: For each number, check if its count in the hash table is greater than 0.
6
Step 6: If the count is greater than 0, decrement the count. Calculate the double of the current number.
7
Step 7: Check if the double exists in the hash table and has a count greater than 0.
8
Step 8: If the double exists, decrement its count and add the original number to the `original` array.
9
Step 9: If the double doesn't exist, return an empty array.
10
Step 10: If the loop completes without returning an empty array, return the `original` 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 log n)

✨ Log-linear - Great for sorting algorithms!

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

Sorting `changed` takes O(n log n) time using efficient sorting algorithms like merge sort or quicksort. The hash table operations (insertion, lookup, deletion) take amortized O(1) time each. The hash table itself can grow to store all unique elements of `changed`, so its space complexity is O(n). The `original` array, in the worst-case, stores n/2 elements, resulting in O(n) space complexity as well.

📖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

Without Sorting

Instead of sorting, iterate through all the elements in `changed` and for each num, if `num*2` is present in the array, add num to original array and remove `num*2` from the array. Requires removing element from list which can be O(n) in each removal. If remove is O(1) (e.g. using a linked list or swapping with last element) then total time complexity can be O(n^2).

Time: O(n^2)Space: O(n)

Trade-offs: Sorting offers a more robust and reliable mechanism to handle cases where doubles are mixed in the `changed` array. This method could be faster in specific cases if removing element is fast enough but typically not worth it due to the n^2 time complexity.

✨

Key Insights

1Insight 1: The length of the `changed` array must be even for it to be a doubled array because each element in `original` contributes two elements to `changed` (itself and its double).
2Insight 2: Sorting the `changed` array simplifies the search for doubled elements. By iterating through the sorted array, we can efficiently check if the doubled value exists and remove both from consideration using a counter.
3Insight 3: Using a hash table (or counter) to keep track of the frequency of each number allows for efficient checking and removal of elements.

📚

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!

Greedy Algorithm

Making the best choice at each step without looking ahead.

Sorting

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

Edge Cases

Edge case 1: `changed` is empty. The solution implicitly handles this correctly as the length check at the beginning will prevent any errors. It will return an empty array, which is the correct result.
Edge case 2: `changed` contains zeros. The solution correctly handles zeros because it counts their occurrences and proceeds to match them with their doubles (which are also zeros).
Edge case 3: `changed = [1, 2, 1, 2]`. This is an interesting case because after processing the first '1', the algorithm looks for '2'. It will successfully find it. Then when processing the second '1', it needs to find another '2', and it will. The algorithm works correctly.
Edge case 4: `changed = [1,2,5,6]`. The length is even, but it is not a doubled array. The algorithm will return an empty array, as expected.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to check if the length of `changed` is even. If the length is odd, it's impossible for it to be a doubled array.

✗Common mistake 2: Not handling the case where the same number appears multiple times. A hash table/counter is necessary to track the frequency of each number.

✗Common mistake 3: Returning the wrong 'original' array if the elements are not processed in the correct order. Sorting helps address this issue, and the hash table tracks the counts correctly.

✗Common mistake 4: Not handling 0 properly. Zero's double is zero, which requires special attention to avoid removing too many or too few zeros.

✅

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?

💼Real-world scenario 1: Data validation. Imagine you receive data pairs where one is expected to be double the other. You can use this algorithm to verify data integrity.

🏦Real-world scenario 2: Financial transactions. Consider a system where each transaction has a corresponding verification record that is twice the transaction amount. You can use this algorithm to validate the integrity of financial records.

🎮Real-world scenario 3: Signal processing. In some signal processing applications, signals might be generated in pairs where one signal is a scaled version (e.g., doubled) of the other. This algorithm could be adapted to identify such paired signals.

💡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

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ 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: June 28, 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 13

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

@CodeNinjaJul 6

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 29

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Find Original Array From Doubled Array"?

For this medium-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?