Recover the Original Array - Solution & Explanation
Problem Statement
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.
Approach Overview
Problem Overview: You receive an array formed by taking every value x from an unknown array and inserting both x - k and x + k. The values are shuffled. The task is to reconstruct the original array and determine the elements x.
Approach 1: Sort and Compare (Sorting + Hash Table) (Time: O(n^2), Space: O(n))
Start by sorting the array. In the transformed array, the smallest value must correspond to x - k for some original element x. Try pairing it with every larger element to guess the value of k. For a candidate pair (nums[0], nums[j]), compute k = (nums[j] - nums[0]) / 2. Only continue if the difference is positive and even. Once a candidate k is chosen, rebuild the original array by greedily matching each value a with a + 2k. A frequency map (from a hash table) tracks remaining elements so each pair is used exactly once.
During reconstruction, iterate through the sorted array. If a number is still unused, treat it as x - k. Check whether x + k (which appears as a + 2k) exists in the frequency map. If it does, decrease counts for both numbers and append a + k to the result. If any required pair is missing, the chosen k is invalid and you try the next candidate.
Sorting simplifies pairing because smaller values are processed first. The hash map ensures constant-time availability checks. The algorithm essentially enumerates valid differences while verifying them using counting. Concepts from sorting, arrays, and hash-based counting drive the solution.
Recommended for interviews: The sorting + enumeration approach is what interviewers typically expect. Brute-force pairing without ordering becomes messy and error-prone. Sorting the array first and validating each possible k shows clear reasoning, controlled enumeration, and correct use of hash maps to enforce pair constraints.
Approach 1: Sort and Compare
By sorting the array, you can effectively guess the potential value of k by comparing and calculating possible values of k from the smallest or largest differences. For each guess of k, attempt reconstructing the original array.
This solution sorts the input nums and tries potential values of k derived from allowable differences between elements. For each k, potential original arrays are constructed and validated before returning.
Complexity
Time Complexity: O(n^2) due to the potential quadratic iteration over elements for each k verification.
Space Complexity: O(n) to store intermediary arrays for validation.
Approach 2: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Sort and Compare | Time Complexity: |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Testing | O(n^3) | O(n) | Conceptual baseline to understand how pairs form original values |
| Sort + Enumerate k with Hash Map | O(n^2) | O(n) | General solution used in interviews and competitive programming |
| Sort + Greedy Pair Matching | O(n^2) | O(n) | When using frequency counting to greedily match a with a+2k |
Video Solution
Recover the Original Array | Leetcode 2122 | Contest 273 | Tricky Solution 🔥🔥🔥🔥 • Coding Decoded • 2,022 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Recover the Original Array easy or hard?
Recover the Original Array Python/Java solution
How to solve Recover the Original Array in O(n)?
What is the best approach for Recover the Original Array?
Is Recover the Original Array asked at Google/Amazon/Meta?
What data structure is used in Recover the Original Array?
What is the time complexity of Recover the Original Array?
Ready to solve this problem?
Practice Recover the Original Array with our built-in code editor and test cases.
Practice on FleetCode