Recover the Original Array solution and explanation
Google
9 more videos on this problem
Recover the Original Array | Leetcode 2122 | Contest 273 | Tricky Solution 🔥🔥🔥🔥Coding Decoded · 15:28 · 2K views
Recover the Original Array | LeetCode Weekly Contest 273 | Hitesh TripathiCode Era · 20:01 · 604 views
Leetcode:Recover the original ArrayCoding For Dummies · 14:38 · 468 views
2122. Recover the Original Array (Leetcode Hard)Programming Live with Larry · 16:51 · 448 views
【每日一题】LeetCode 2122. Recover the Original ArrayHuifeng Guan · 25:21 · 396 views
Recover the Original Array (Leetcode Weekly 273)Soumya Bhattacharjee · 7:42 · 176 views
Leetcode 2122. Recover the Original Array (2 pointers and greedy)LetsCode · 22:10 · 18 views
Recover the Original Array LeetCode 2122algorithmswala · 3:18 · 6 views
LeetCode 2122: Recover the Original ArrayAlitaCode · 30:09 · 2 views
2122 recover the original arrayCodePen · 1:10 · 2 views
The problem
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.
def recoverArray(nums):
nums.sort()
n = len(nums) // 2
for i in range(1, len(nums)):
if (nums[i] - nums[0]) % 2 != 0:
continue
k = (nums[i] - nums[0]) // 2
if k == 0:
continue
arr = []
used = [False] * len(nums)
valid = True
for j in range(len(nums)):
if used[j]:
continue
target = nums[j] + 2*k
try:
idx = nums.index(target)
except ValueError:
valid = False
break
if used[idx]:
continue
arr.append(nums[j] + k)
used[j] = used[idx] = True
if valid:
return arr
return []
nums = [2, 10, 6, 4, 8, 12]
print(recoverArray(nums))import java.util.*;
public class Solution {
public int[] recoverArray(int[] nums) {
Arrays.sort(nums);
int n = nums.length / 2;
for (int i = 1; i < nums.length; i++) {
if ((nums[i] - nums[0]) % 2 != 0) continue;
int k = (nums[i] - nums[0]) / 2;
if (k == 0) continue;
int[] arr = new int[n];
boolean[] used = new boolean[nums.length];
Arrays.fill(used, false);
boolean valid = true;
int j = 0;
for (int num : nums) {
if (used[j]) continue;
int target = num + 2 * k;
int idx = -1;
for (int m = 0; m < nums.length; m++) {
if (!used[m] && nums[m] == target) {
idx = m;
break;
}
}
if (idx == -1) {
valid = false;
break;
}
arr[j++] = num + k;
used[j] = used[idx] = true;
}
if (valid) return arr;
}
return new int[0];
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {2, 10, 6, 4, 8, 12};
int[] result = sol.recoverArray(nums);
System.out.println(Arrays.toString(result));
}
}#include <vector>
#include <algorithm>
using namespace std;
vector<int> recoverArray(vector<int>& nums) {
sort(nums.begin(), nums.end());
int n = nums.size() / 2;
for (int i = 1; i < nums.size(); i++) {
if ((nums[i] - nums[0]) % 2 != 0) continue;
int k = (nums[i] - nums[0]) / 2;
if (k == 0) continue;
vector<int> result;
vector<bool> used(nums.size(), false);
bool valid = true;
result.reserve(n);
for (int j = 0; j < nums.size(); ++j) {
if (used[j]) continue;
auto it = find(nums.begin(), nums.end(), nums[j] + 2 * k);
if (it != nums.end() && !used[it - nums.begin()]) {
used[j] = used[it - nums.begin()] = true;
result.push_back(nums[j] + k);
} else {
valid = false;
break;
}
}
if (valid) return result;
}
return {};
}
int main() {
vector<int> nums = {2, 10, 6, 4, 8, 12};
auto result = recoverArray(nums);
printf("[");
for (int i = 0; i < result.size(); i++) {
printf("%d%s", result[i], i == result.size() - 1 ? "" : ", ");
}
printf("]\n");
return 0;
}const recoverArray = (nums) => {
nums.sort((a, b) => a - b);
const n = nums.length / 2;
for (let i = 1; i < nums.length; i++) {
if ((nums[i] - nums[0]) % 2 !== 0) continue;
const k = (nums[i] - nums[0]) / 2;
if (k <= 0) continue;
const arr = [];
const used = Array(nums.length).fill(false);
let valid = true;
for (let j = 0; j < nums.length; j++) {
if (used[j]) continue;
const target = nums[j] + 2 * k;
const index = nums.indexOf(target);
if (index === -1 || used[index]) {
valid = false;
break;
}
arr.push(nums[j] + k);
used[j] = used[index] = true;
}
if (valid) return arr;
}
return [];
};
const nums = [2, 10, 6, 4, 8, 12];
console.log(recoverArray(nums));#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int* recoverArray(int* nums, int numsSize, int* returnSize) {
qsort(nums, numsSize, sizeof(int), compare);
int n = numsSize / 2;
for (int i = 1; i < numsSize; i++) {
int k = (nums[i] - nums[0]) / 2;
if (k <= 0) continue;
int *used = calloc(numsSize, sizeof(int));
int *arr = malloc(n * sizeof(int));
int found = 1;
int j = 0;
for (int l = 0; l < numsSize; l++) {
if (used[l]) continue;
int target = nums[l] + 2*k;
int position = -1;
for (int m = 0; m < numsSize; m++) {
if (!used[m] && nums[m] == target) {
position = m;
break;
}
}
if (position == -1) {
found = 0;
break;
}
arr[j++] = nums[l] + k;
used[l] = used[position] = 1;
}
free(used);
if (found) {
*returnSize = n;
return arr;
} else {
free(arr);
}
}
return NULL;
}
int main() {
int nums[] = {2, 10, 6, 4, 8, 12};
int returnSize;
int* result = recoverArray(nums, 6, &returnSize);
printf("[");
for (int i = 0; i < returnSize; i++) {
printf("%d%s", result[i], i == returnSize - 1 ? "": ", ");
}
printf("]\n");
free(result);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public int[] RecoverArray(int[] nums) {
Array.Sort(nums);
int n = nums.Length / 2;
for (int i = 1; i < nums.Length; i++) {
if ((nums[i] - nums[0]) % 2 != 0) continue;
int k = (nums[i] - nums[0]) / 2;
if (k <= 0) continue;
List<int> arr = new List<int>();
bool[] used = new bool[nums.Length];
bool valid = true;
for (int j = 0; j < nums.Length; j++) {
if (used[j]) continue;
int target = nums[j] + 2 * k;
int index = Array.IndexOf(nums, target);
if (index == -1 || used[index]) {
valid = false;
break;
}
arr.Add(nums[j] + k);
used[j] = used[index] = true;
}
if (valid) return arr.ToArray();
}
return new int[0];
}
public static void Main(string[] args) {
Solution sol = new Solution();
int[] nums = {2, 10, 6, 4, 8, 12};
int[] result = sol.RecoverArray(nums);
Console.WriteLine("[{0}]", string.Join(", ", result));
}
}Sort the input nums and derive potential k values by iterating over differences between sorted elements. Attempt to reconstruct an array for each valid k, and return once validation succeeds.
Time Complexity: O(n^2): Requires checking each possible pair derived from sorted differences.
Space Complexity: O(n) to manage tracking of used elements and interim validation arrays.
Approach 2: Default Approach
func recoverArray(nums []int) []int {
sort.Ints(nums)
for i, n := 1, len(nums); i < n; i++ {
d := nums[i] - nums[0]
if d == 0 || d%2 == 1 {
continue
}
vis := make([]bool, n)
vis[i] = true
ans := []int{(nums[0] + nums[i]) >> 1}
for l, r := 1, i+1; r < n; l, r = l+1, r+1 {
for l < n && vis[l] {
l++
}
for r < n && nums[r]-nums[l] < d {
r++
}
if r == n || nums[r]-nums[l] > d {
break
}
vis[r] = true
ans = append(ans, (nums[l]+nums[r])>>1)
}
if len(ans) == (n >> 1) {
return ans
}
}
return []int{}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sort and Compare | Time Complexity: |
| Default Approach | – |
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 |
Frequently asked questions
Is Recover the Original Array easy or hard?
Recover the Original Array is rated Hard on LeetCode. The challenge comes from identifying the correct value of k and validating pairs efficiently while handling duplicates and maintaining element counts.
Recover the Original Array Python/Java solution
Most implementations follow the same logic across languages: sort the array, enumerate candidate k values, then use a hash map to match pairs a and a + 2k. Python uses collections.Counter, while Java typically uses HashMap for frequency tracking.
How to solve Recover the Original Array in O(n)?
An O(n) solution is generally not feasible because the algorithm must test multiple candidate values of k derived from pair differences. Each candidate requires verifying pairings across the array. The practical optimal solution is O(n^2) after sorting.
What is the best approach for Recover the Original Array?
The most reliable approach sorts the array and enumerates possible values of k using differences with the smallest element. For each candidate k, a hash map validates whether every value a can be paired with a + 2k. This approach runs in O(n^2) time with O(n) extra space and is the expected interview solution.
Is Recover the Original Array asked at Google/Amazon/Meta?
Problems involving array reconstruction, pair differences, and frequency matching appear in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, the underlying techniques—sorting, hash maps, and greedy pairing—are common interview patterns.
What data structure is used in Recover the Original Array?
A hash table (frequency map) is the main data structure. It tracks how many times each value appears so elements can be paired correctly as a and a + 2k. Sorting the array beforehand helps process elements in deterministic order.
What is the time complexity of Recover the Original Array?
The common sorting and enumeration solution runs in O(n^2) time. Sorting the array takes O(n log n), and testing each candidate k requires scanning the array with hash map checks, which leads to O(n^2) overall. Space complexity is O(n) for frequency tracking.