To solve the problem, find if a given shuffled array is a doubled array. Use hash lookup to check pairs of numbers and eliminate them efficiently. If any pair is missing, return an empty 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'.
How GhostInterview Helps
- GhostInterview provides an efficient approach to solving array-based problems using hash tables and greedy algorithms.
- The platform helps by guiding you through handling edge cases, such as ensuring the array length is even for valid results.
- With detailed walkthroughs, GhostInterview assists in understanding the time and space complexities, helping you optimize your solution.
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
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.
Need direct help with Find Original Array From Doubled Array instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Find Original Array From Doubled 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
Minimize operations to make all array elements zero by subtracting equal amounts in each operation.
Open problem page#1481 Least Number of Unique Integers after K RemovalsFind the least number of unique integers after removing exactly k elements from an array using efficient frequency counting and greedy strategy.
Open problem page#2554 Maximum Number of Integers to Choose From a Range IDetermine the maximum count of integers from 1 to n avoiding banned numbers while keeping the sum under maxSum.
Open problem page