Recover the Original Array

The Recover the Original Array problem requires reconstructing an original array from two unknown subsets. You must figure out how to combine these subsets correctly by selecting a valid integer k. The solution leverages array scanning with hash lookups, making the task both challenging and rewarding.

Problem Statement

Alice had an array arr with n positive integers. She selected an arbitrary integer k and used it to create two new arrays: lower and higher. The lower array contains all elements of arr that are less than or equal to k, while the higher array contains elements strictly greater than k. Alice lost all three arrays but remembers the integers in lower and higher, but not which belongs to which. Your task is to recover the original array arr.

Given a 2n-length array nums, where exactly n elements came from lower and the remaining from higher, your goal is to return the original array arr. If multiple solutions exist, return any valid solution. The array should be reconstructed by finding the integer k that satisfies the relationship between lower and higher arrays.

Examples

Example 1

Input: nums = [2,10,6,4,8,12]

Output: [3,7,11]

If arr = [3,7,11] and k = 1, we get lower = [2,6,10] and higher = [4,8,12]. Combining lower and higher gives us [2,6,10,4,8,12], which is a permutation of nums. Another valid possibility is that arr = [5,7,9] and k = 3. In that case, lower = [2,4,6] and higher = [8,10,12].

Example 2

Input: nums = [1,1,3,3]

Output: [2,2]

If arr = [2,2] and k = 1, we get lower = [1,1] and higher = [3,3]. Combining lower and higher gives us [1,1,3,3], which is equal to nums. Note that arr cannot be [1,3] because in that case, the only possible way to obtain [1,1,3,3] is with k = 0. This is invalid since k must be positive.

Example 3

Input: nums = [5,435]

Output: [220]

The only possible combination is arr = [220] and k = 215. Using them, we get lower = [5] and higher = [435].

Constraints

• 2 * n == nums.length
• 1 <= n <= 1000
• 1 <= nums[i] <= 109
• The test cases are generated such that there exists at least one valid array arr.

Solution Approach

Fix the value of k

Start by fixing the value of k and divide nums into two arrays: one for values less than or equal to k (lower) and one for values greater than k (higher). Ensure that each subset is a permutation of the values from the original array.

Use Hash Table for Validation

To check if the arrays lower and higher are valid for a particular k, use a hash table to track the frequency of elements. Verify if the partitioning leads to two distinct subsets with no overlap, ensuring the recovery of the original array.

Iterate over possible k values

For each possible value of k, check if it can result in valid lower and higher arrays. This involves verifying if each element from the nums array can be placed into either the lower or higher arrays in a consistent manner.

Complexity Analysis

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

The time complexity is primarily influenced by the number of elements in nums and the range of possible k values. Since nums has 2n elements, and checking each possible k involves scanning the array, the overall time complexity is O(n^2). Space complexity depends on the usage of a hash table and auxiliary arrays, resulting in O(n) space usage.

What Interviewers Usually Probe

• The candidate should demonstrate an understanding of partitioning an array based on a value of k.
• Look for a clear explanation of using hash tables for validation of partitioning.
• Check if the candidate can describe the time complexity and justify it with respect to the problem constraints.

Common Pitfalls or Variants

Common pitfalls

• Failing to correctly partition the nums array based on k, leading to incorrect lower and higher arrays.
• Not using the hash table efficiently to track the frequency of numbers, resulting in slower or incorrect solutions.
• Overlooking the possibility of multiple valid solutions and missing edge cases where multiple values of k are valid.

Follow-up variants

• What if the original array arr is allowed to contain duplicate elements?
• How would the solution change if we had a more constrained range of k values?
• Consider a scenario where nums contains some elements in a non-sorted order—how would that affect the approach?

FAQ

How do I approach solving the Recover the Original Array problem?

Start by fixing the value of k, and then partition nums into lower and higher arrays. Use a hash table to verify if this partitioning is valid, and iterate through possible k values to find a correct solution.

What is the main challenge in the Recover the Original Array problem?

The challenge lies in efficiently partitioning the nums array using an arbitrary k and ensuring that the lower and higher arrays are valid. Hash tables are key to tracking the frequency of elements.

What is the time complexity of the Recover the Original Array problem?

The time complexity is O(n^2) due to iterating over possible values of k and partitioning the nums array each time. However, optimizations can be made depending on the implementation.

Are there multiple valid solutions to the Recover the Original Array problem?

Yes, the problem allows for multiple valid solutions as long as the partitioning leads to a correct original array. Any valid partition of nums into lower and higher arrays is acceptable.

Can I use sorting to solve the Recover the Original Array problem?

Sorting could help in certain cases, but the primary solution relies on scanning and hash lookups to partition nums efficiently. Sorting may not always be optimal in terms of time complexity.