Recover the Original Array
HardPrompt
Alice had a 0-indexed array arr consisting of n positive integers. She chose an arbitrary positive integer k and created two new 0-indexed integer arrays lower and higher in the following manner:
lower[i] = arr[i] - k, for every indexiwhere0 <= i < nhigher[i] = arr[i] + k, for every indexiwhere0 <= i < n
Unfortunately, Alice lost all three arrays. However, she remembers the integers that were present in the arrays lower and higher, but not the array each integer belonged to. Help Alice and recover the original array.
Given an array nums consisting of 2n integers, where exactly n of the integers were present in lower and the remaining in higher, return the original array arr. In case the answer is not unique, return any valid array.
Note: The test cases are generated such that there exists at least one valid array arr.
Example 1:
Input: nums = [2,10,6,4,8,12]
Output: [3,7,11]
Explanation:
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]
Explanation:
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]
Explanation:
The only possible combination is arr = [220] and k = 215. Using them, we get lower = [5] and higher = [435].
Constraints:
2 * n == nums.length1 <= n <= 10001 <= nums[i] <= 109- The test cases are generated such that there exists at least one valid array
arr.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach explores all possible ways to partition the 2n numbers into a lower array and a higher array, each of size n. For each partition, it checks if it could have been generated from some original array arr and a positive integer k.
Algorithm
- Generate all possible subsets of
numsthat have a size ofn. Each such subset is a candidate for thelowerarray. - For each candidate
lowerarray, the remainingnelements ofnumsform the candidatehigherarray. - Sort both the candidate
lowerandhigherarrays. - Calculate the difference
d = higher[0] - lower[0]. - If
dis not a positive value, this partition is invalid, so we discard it and move to the next one. - Check if this difference
dis consistent for all pairs of elements, i.e.,higher[i] - lower[i] == dfor alli. - If the difference is consistent, we have found a valid
2k = d. The original arrayarrcan be reconstructed asarr[i] = lower[i] + k(wherek = d / 2). - Since a solution is guaranteed to exist, this process will eventually find it, and we can return the reconstructed
arr.
Walkthrough
The most straightforward, yet impractical, way to solve the problem is to try every possible assignment of the 2n numbers in nums to either the lower set or the higher set. The number of ways to choose n elements for the lower set from 2n elements is given by the binomial coefficient "2n choose n" (C(2n, n)).
The algorithm would recursively generate all subsets of nums of size n. Each such subset is a candidate for the lower array. The remaining n elements would form the higher array.
For each candidate partition (lower_candidate, higher_candidate):
- Sort both
lower_candidateandhigher_candidatearrays. - Calculate the difference
d = higher_candidate[0] - lower_candidate[0]. - Check if this difference
dis positive and consistent for all other pairs of elements. That is, check ifhigher_candidate[i] - lower_candidate[i] == dfor allifrom1ton-1. - If the difference is consistent and positive, we have found a valid
2k = d. The original arrayarrcan be reconstructed asarr[i] = lower_candidate[i] + k = lower_candidate[i] + d/2. Since a solution is guaranteed to exist, we can return thisarr.
This method is too slow for the given constraints but represents a foundational brute-force solution.
Complexity
Time
O(C(2n, n) * n log n) Generating all partitions takes `C(2n, n)` time. For each partition, we perform sorting, which takes `O(n log n)`, and a linear scan, which takes `O(n)`. The sorting step dominates the work done per partition. This complexity is exponential and thus not feasible.
Space
O(n) This space is required to store a single partition (both `lower` and `higher` candidate arrays) during processing.
Trade-offs
Pros
It's a direct, brute-force interpretation of the problem definition.
It is guaranteed to find a valid solution.
Cons
Extremely inefficient due to its exponential time complexity.
The number of partitions grows astronomically with
n, making it infeasible for the given constraints (e.g., forn=15,2n=30,C(30, 15)is over 155 million).
Solutions
Solution
class Solution {public int[] recoverArray(int[] nums) { Arrays.sort(nums); for (int i = 1, n = nums.length; i < n; ++i) { int d = nums[i] - nums[0]; if (d == 0 || d % 2 == 1) { continue; } boolean[] vis = new boolean[n]; vis[i] = true; List<Integer> t = new ArrayList<>(); t.add((nums[0] + nums[i]) >> 1); for (int l = 1, r = i + 1; r < n; ++l, ++r) { while (l < n && vis[l]) { ++l; } while (r < n && nums[r] - nums[l] < d) { ++r; } if (r == n || nums[r] - nums[l] > d) { break; } vis[r] = true; t.add((nums[l] + nums[r]) >> 1); } if (t.size() == (n >> 1)) { int[] ans = new int[t.size()]; int idx = 0; for (int e : t) { ans[idx++] = e; } return ans; } } return null; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.