Recover the Original Array

Recover the Original Array

What is this problem about?

The Recover the Original Array problem gives you a sorted array that was created by combining [arr[i]-k, arr[i]+k] for each element of the original array. Reconstruct the original array. This hard coding problem tries all valid k values (derived from the first element's possible pairings) and checks feasibility with a frequency map. The array, hash table, sorting, two pointers, and enumeration interview pattern is the core.

Why is this asked in interviews?

Google asks this because it tests the "enumerate possible k values, validate each" strategy. The first element of the sorted combined array must pair with some other element (offset by 2k). Trying each pairing as a candidate k narrows the search space dramatically.

Algorithmic pattern used

Enumerate k + frequency validation. Sort the combined array. The smallest element must pair with another element (at offset 2k from it). Enumerate all k = (combined[j] - combined[0]) / 2 for j=1,2,...n-1 (only if even difference and k>0). For each valid k: use a frequency map to greedily pair x with x+2k for each element from smallest to largest. If all pairs match perfectly, this k gives the original array.

Example explanation

changed=[2,10,6,4,8,12] (sorted: [2,4,6,8,10,12]). n=3.

• Try k=(4-2)/2=1: pairs (2,4),(4,6),(6,8),(8,10),(10,12)... check feasibility.
• Try k=(6-2)/2=2: pairs (2,6),(4,8),(6,10),(8,12). All match. k=2. Original=[2,4,6] (arr[i] = avg of pair). Result: [2,4,6].

Common mistakes candidates make

• Not requiring k > 0 (k=0 means identical pairs which may not reconstruct uniquely).
• Not sorting before enumeration.
• Incorrect pairing: original element = (x + x+2k) / 2 = x + k.
• Not handling the case where the same element could pair with itself.

Interview preparation tip

Recover the Original Array uses "enumerate and validate" — a powerful technique when direct computation is hard but validation is easy. Enumerate candidate k values from the first element's pairings, then validate each O(n) with a frequency map. Practice similar enumeration problems: "find the duplicate," "reconstruct from modified array." The first-element constraint is key for narrowing candidates.