How do you solve Find Original Array From Doubled Array on LeetCode?

Find Original Array From Doubled Array (LeetCode #2007) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: If the length of the changed array is odd, it cannot be a doubled array.

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

The optimal solution for Find Original Array From Doubled Array runs in O(n log n) time and uses O(n) space. The time complexity is O(n log n) due to sorting the array, and the space complexity is O(n) for storing the frequency map.

What is the brute force solution for Find Original Array From Doubled Array?

The brute force approach for Find Original Array From Doubled Array is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every element in the array to see if its double exists in the array. This is simple but inefficient since it requires checking each element against all others. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Find Original Array From Doubled Array?

Find Original Array From Doubled Array uses the following concepts: Array, Hash Table, Greedy, Sorting. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Find Original Array From Doubled Array?

Always consider edge cases, such as empty or odd-length arrays. Explain your thought process clearly while coding; it helps the interviewer understand your approach. Use a HashMap for counting occurrences when dealing with pairs or duplicates.

What are common mistakes when solving Find Original Array From Doubled Array?

Not checking if the length of the changed array is even. Failing to account for the case where an element's double is not present.

#2007

Find Original Array From Doubled Array

Medium

ArrayHash TableGreedySortingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

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

The optimal solution uses a HashMap to count occurrences of each number, allowing us to efficiently check and remove elements and their doubles in linear time.

⚙️

Algorithm

6 steps

1Step 1: Create a frequency map (HashMap) to count occurrences of each number in the changed array.
2Step 2: Sort the keys of the frequency map to handle smaller numbers first.
3Step 3: For each number, check if its double exists in the map with a sufficient count.
4Step 4: If it does, add the number to the original array and decrease the counts accordingly.
5Step 5: If any number cannot be paired with its double, return an empty array.
6Step 6: Return the original array if all checks pass.

solution.py13 lines

1# Full working Python code
2
3def findOriginalArray(changed):
4    if len(changed) % 2 != 0:
5        return []
6    count = Counter(changed)
7    original = []
8    for num in sorted(count.keys()):
9        if count[num] > count[num * 2]:
10            return []
11        original.extend([num] * (count[num]))
12        count[num * 2] -= count[num]
13    return original

ℹ

Complexity note: The time complexity is O(n log n) due to sorting the array, and the space complexity is O(n) for storing the frequency map.

1If the length of the changed array is odd, it cannot be a doubled array.
2The smallest element in the changed array is guaranteed to be part of the original array.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.