Recover the Original Array

Hard

#1932Time: 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.

Patterns

Two Pointers Enumeration

Algorithms

Sorting

Data structures

Array Hash Table

Prompt

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 index i where 0 <= i < n
higher[i] = arr[i] + k, for every index i where 0 <= 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.length
1 <= n <= 1000
1 <= nums[i] <= 10⁹
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 nums that have a size of n. Each such subset is a candidate for the lower array.
For each candidate lower array, the remaining n elements of nums form the candidate higher array.
Sort both the candidate lower and higher arrays.
Calculate the difference d = higher[0] - lower[0].
If d is not a positive value, this partition is invalid, so we discard it and move to the next one.
Check if this difference d is consistent for all pairs of elements, i.e., higher[i] - lower[i] == d for all i.
If the difference is consistent, we have found a valid 2k = d. The original array arr can be reconstructed as arr[i] = lower[i] + k (where k = 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_candidate and higher_candidate arrays.
Calculate the difference d = higher_candidate[0] - lower_candidate[0].
Check if this difference d is positive and consistent for all other pairs of elements. That is, check if higher_candidate[i] - lower_candidate[i] == d for all i from 1 to n-1.
If the difference is consistent and positive, we have found a valid 2k = d. The original array arr can be reconstructed as arr[i] = lower_candidate[i] + k = lower_candidate[i] + d/2. Since a solution is guaranteed to exist, we can return this arr.

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., for n=15, 2n=30, C(30, 15) is over 155 million).

This approach significantly improves upon the naive brute force by using a key insight: after sorting the nums array, the smallest element nums[0] must belong to the lower array. This reduces the search space for k dramatically. We can iterate through possible partners for nums[0], which gives us a candidate for k, and then efficiently verify this k for the entire array in linear time.

Algorithm

Sort the input array nums in non-decreasing order.
The smallest element, nums[0], must be a lower element. Its corresponding higher element is nums[0] + 2k.
Iterate with an index j from 1 to 2n-1. Each nums[j] is a candidate for being the partner of nums[0].
For each j, calculate the potential difference diff = nums[j] - nums[0].
If diff is zero, negative, or odd, it cannot represent 2k (since k must be a positive integer). Continue to the next j.
If diff is valid, we have a candidate k = diff / 2. We must now verify if this k can form n pairs (x, x + 2k) from the numbers in nums.
To verify k, use a frequency map (e.g., a HashMap) to store the counts of each number in nums.
Iterate through the sorted nums array. For each num: a. If its count in the map is zero, it has already been used as a partner, so skip it. b. Otherwise, treat num as a lower element. Decrement its count in the map. c. Find its required partner p = num + 2k. d. Check if p exists in the map with a positive count. If yes, decrement p's count and add the original value num + k to our result array. e. If p does not exist in the map with a positive count, this candidate k is incorrect. Abort the verification for this k and try the next j.
If the verification process completes and we have formed an array of size n, we have found a valid solution. Return it.

Walkthrough

The algorithm begins by sorting the nums array. This is a critical step because it establishes that nums[0] must be a lower value, say arr[i] - k. If it were a higher value, arr[j] + k, then its corresponding lower value, arr[j] - k, would be smaller, which contradicts nums[0] being the minimum element in the array.

The partner for nums[0] is nums[0] + 2k. This partner must be one of the other elements in the array, say nums[j] for some j > 0. We can iterate through j from 1 to 2n-1 to test each nums[j] as a potential partner.

For each j, we calculate a potential difference diff = nums[j] - nums[0]. This diff would be equal to 2k. For k to be a positive integer, diff must be positive and even. If not, we discard this j and move to the next.

If diff is valid, we have a candidate k = diff / 2. We must now verify if this k can explain the entire nums array. This verification can be done efficiently in O(n) time. We use a frequency map (like a HashMap) to store the counts of each number in nums. We then iterate through the sorted nums array. For each number num, if its count is positive, we treat it as a lower value. We find its potential higher partner num + 2k. If this partner also exists in the map with a positive count, we've found a valid pair. We decrement the counts of both num and its partner in the map and add the original value num + k to our result array.

If at any point we cannot find a partner for a number, the candidate k is incorrect. We stop and try the next j. Since the problem guarantees a solution exists, this process will find one.

1import java.util.Arrays;2import java.util.Map;3import java.util.HashMap;4import java.util.ArrayList;5import java.util.List;6 7class Solution {8    public int[] recoverArray(int[] nums) {9        int n = nums.length / 2;10        Arrays.sort(nums);11 12        for (int j = 1; j < nums.length; j++) {13            int diff = nums[j] - nums[0];14            if (diff <= 0 || diff % 2 != 0) {15                continue;16            }17            18            int k = diff / 2;19            int[] result = check(nums, k, n);20            if (result.length == n) {21                return result;22            }23        }24        return new int[0]; // Should not be reached given the problem constraints25    }26 27    private int[] check(int[] nums, int k, int n) {28        List<Integer> resList = new ArrayList<>();29        Map<Integer, Integer> freq = new HashMap<>();30        for (int num : nums) {31            freq.put(num, freq.getOrDefault(num, 0) + 1);32        }33 34        for (int i = 0; i < nums.length; i++) {35            int num = nums[i];36            if (freq.get(num) == 0) {37                continue;38            }39            40            freq.put(num, freq.get(num) - 1);41            int partner = num + 2 * k;42            43            if (freq.getOrDefault(partner, 0) > 0) {44                freq.put(partner, freq.get(partner) - 1);45                resList.add(num + k);46            } else {47                return new int[0]; // Invalid k, this partition is not possible48            }49        }50 51        // This check is technically redundant if the above loop completes successfully52        // for a valid k, as resList will always have n elements.53        if (resList.size() == n) {54            int[] resultArr = new int[n];55            for (int i = 0; i < n; i++) {56                resultArr[i] = resList.get(i);57            }58            return resultArr;59        }60        return new int[0];61    }62}

Complexity

Time

O(n^2) Sorting the `nums` array takes `O(n log n)`. The main part of the algorithm is the outer loop that iterates up to `2n-1` times (`O(n)`) to select a candidate `k`. Inside this loop, the `check` function is called. This function builds a frequency map (`O(n)`) and then iterates through `nums` again (`O(n)`), performing constant-time hash map operations on average. So, the verification step is `O(n)`. The total complexity is `O(n log n) + O(n) * O(n) = O(n^2)`.

Space

O(n) The frequency map used for verification can store up to `2n` distinct numbers in the worst case. The result list also requires `O(n)` space. Thus, the space complexity is `O(n)`.

Trade-offs

Pros

Vastly more efficient than the naive exponential approach.
Correct and guaranteed to find the solution under the problem's constraints.
The logic is straightforward and relatively simple to implement.

Cons

The O(n^2) time complexity might be a concern for significantly larger constraints, although it is efficient enough for the given problem constraints (n <= 1000).

Solutions

Solution

1class Solution {2public3  int[] recoverArray(int[] nums) {4    Arrays.sort(nums);5    for (int i = 1, n = nums.length; i < n; ++i) {6      int d = nums[i] - nums[0];7      if (d == 0 || d % 2 == 1) {8        continue;9      }10      boolean[] vis = new boolean[n];11      vis[i] = true;12      List<Integer> t = new ArrayList<>();13      t.add((nums[0] + nums[i]) >> 1);14      for (int l = 1, r = i + 1; r < n; ++l, ++r) {15        while (l < n && vis[l]) {16          ++l;17        }18        while (r < n && nums[r] - nums[l] < d) {19          ++r;20        }21        if (r == n || nums[r] - nums[l] > d) {22          break;23        }24        vis[r] = true;25        t.add((nums[l] + nums[r]) >> 1);26      }27      if (t.size() == (n >> 1)) {28        int[] ans = new int[t.size()];29        int idx = 0;30        for (int e : t) {31          ans[idx++] = e;32        }33        return ans;34      }35    }36    return null;37  }38}

1class Solution {2public:3  vector<int> recoverArray(vector<int> &nums) {4    sort(nums.begin(), nums.end());5    for (int i = 1, n = nums.size(); i < n; ++i) {6      int d = nums[i] - nums[0];7      if (d == 0 || d % 2 == 1)8        continue;9      vector<bool> vis(n);10      vis[i] = true;11      vector<int> ans;12      ans.push_back((nums[0] + nums[i]) >> 1);13      for (int l = 1, r = i + 1; r < n; ++l, ++r) {14        while (l < n && vis[l])15          ++l;16        while (r < n && nums[r] - nums[l] < d)17          ++r;18        if (r == n || nums[r] - nums[l] > d)19          break;20        vis[r] = true;21        ans.push_back((nums[l] + nums[r]) >> 1);22      }23      if (ans.size() == (n >> 1))24        return ans;25    }26    return {};27  }28};

1class Solution:2    def recoverArray(self, nums: List[int]) -> List[int]: nums . sort() n = len(nums) for i in range(1, n): d = nums[i] - nums[0] if d == 0 or d % 2 == 1: continue vis = [False] * n vis[i] = True ans = [(nums[0] + nums[i]) >> 1] l, r = 1, i + 1 while r < n: while l < n and vis[l]: l += 1 while r < n and nums[r] - nums[l] < d: r += 1 if r == n or nums[r] - nums[l] > d: break vis[r] = True ans . append((nums[l] + nums[r]) >> 1) l, r = l + 1, r + 1 if len(ans) == (n >> 1): return ans return []

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.

← Previous

Previous problem

Next problem