#2007

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Find Original Array From Doubled Array

Given a shuffled array, determine if it is a doubled array and find the original array.

Problem Statement

You are given an integer array called 'changed' that is formed by transforming an array 'original'. Each element in 'original' is duplicated and placed in 'changed' in any order. The goal is to determine whether 'changed' can represent a doubled array of some 'original', and return 'original' if possible.

If 'changed' cannot be a doubled array, return an empty array. The elements in 'original' can be returned in any order. If 'changed' is a valid doubled array, you should be able to pair each element with its double and remove both from 'changed' until the array is empty.

Examples

Example 1

Input: changed = [1,3,4,2,6,8]

Output: [1,3,4]

One possible original array could be [1,3,4]:

Twice the value of 1 is 1 * 2 = 2.
Twice the value of 3 is 3 * 2 = 6.
Twice the value of 4 is 4 * 2 = 8. Other original arrays could be [4,3,1] or [3,1,4].

Example 2

Input: changed = [6,3,0,1]

Output: []

changed is not a doubled array.

Example 3

Input: changed = [1]

Output: []

changed is not a doubled array.

Constraints

1 <= changed.length <= 105
0 <= changed[i] <= 105

Solution Approach

Sort and Use Hash Table

Sort the 'changed' array and then use a hash table to count the frequency of each number. For each element, check if its double exists in the hash table, and if so, remove both elements from the hash table.

Greedy Element Removal

After sorting 'changed', greedily try to remove each number along with its double. If at any point a number cannot be paired with its double, return an empty array.

Edge Case Handling

Ensure that cases where 'changed' has an odd number of elements are handled, as they cannot possibly be a valid doubled array. If the length is odd, immediately return an empty array.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the sorting step, which is O(n log n), and the hash table lookup and removal steps, which are O(n). Therefore, the overall time complexity is O(n log n). The space complexity is O(n) due to the hash table storage.

What Interviewers Usually Probe

Checks if the candidate is familiar with hash tables and greedy algorithms.
Evaluates how efficiently the candidate uses sorting to solve the problem.
Assesses whether the candidate can handle edge cases, like arrays with odd lengths.

Common Pitfalls or Variants

Common pitfalls

Not sorting the array before performing the hash lookup, which could lead to incorrect pairings.
Overlooking edge cases like arrays of odd lengths, which cannot form a valid doubled array.
Failing to check for the presence of the double before removing elements from the hash table, leading to errors.

Follow-up variants

Change the problem to allow multiple instances of the same number in 'original'.
Instead of sorting, use a priority queue to handle the number pairing more efficiently.
Extend the problem by checking if the array is 'k-doubled', meaning each element should have a multiple of 'k'.

FAQ

What is the main pattern to solve the 'Find Original Array From Doubled Array' problem?

The main pattern is array scanning combined with hash table lookups, which ensures efficient pairing and removal of elements.

What happens if the input array is of odd length?

An array of odd length cannot be a doubled array, so the solution should return an empty array immediately.

How do I handle edge cases for this problem?

Check for odd-length arrays and ensure that every number in the array can be paired with its double before removing it.

Can the elements in the original array be returned in any order?

Yes, the elements of the original array can be returned in any order as long as the pairing holds.

How can sorting the array help in this problem?

Sorting the array helps in greedily matching the smallest numbers first, ensuring that each number can be paired with its double efficiently.

terminal

Solution

Solution 1: Sorting

We notice that if the array `changed` is a double array, then the smallest element in the array `changed` must also be an element in the original array. Therefore, we can first sort the array `changed`, and then start from the first element to traverse the array `changed` in ascending order.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def findOriginalArray(self, changed: List[int]) -> List[int]:
        changed.sort()
        cnt = Counter(changed)
        ans = []
        for x in changed:
            if cnt[x] == 0:
                continue
            cnt[x] -= 1
            if cnt[x << 1] <= 0:
                return []
            cnt[x << 1] -= 1
            ans.append(x)
        return ans

Continue Practicing

#2357 make array zero by subtracting equal amounts #1481 least number of unique integers after k removals #2554 maximum number of integers to choose from a range i