Recover the Original Array

LeetCode 2241 | Difficulty: Hard

Hard

Problem Description

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^9`

- The test cases are generated such that there exists **at least one** valid array `arr`.

Topics: Array, Hash Table, Two Pointers, Sorting, Enumeration

---

Approach

Two Pointers

Use two pointers to traverse the array, reducing the search space at each step. This avoids the need for nested loops, bringing complexity from O(n²) to O(n) or O(n log n) if sorting is involved.

When to use

Array is sorted or can be sorted, and you need to find pairs/triplets that satisfy a condition.

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 394 ms)

Metric	Value
Runtime	394 ms
Memory	45.6 MB
Date	2022-02-01

Solution

public class Solution {
    public int[] RecoverArray(int[] nums) {
    int n = nums.Length;
    if(n%2 != 0) return new int[0];
    Array.Sort(nums);
    int[] result = new int[n/2];

    Dictionary<int, int> counts = new Dictionary<int, int>();
    foreach (var num in nums)
    {
        if (counts.ContainsKey(num)) counts[num]++;
        else counts.Add(num, 1);
    }

    for (int i = 1; i < n; i++)
    {
        int k = nums[i] - nums[0];
        if(k== 0 || k%2 != 0) continue; 
        k = k/2;
        if(IsKValid(nums, k, new Dictionary<int, int>(counts), result ))
        {
            return result;
        }
    }
    return result;
}

private bool IsKValid(int[] nums, int k, Dictionary<int, int> counts, int[] result)
{   
    int carry = 2*k;
    int index=0;
    foreach (var num in nums)
    {
        if(counts[num]==0) continue;
        // lower(num) = value-k , higher = value+k so value = num+k
        // higher = num+k+k = 2*k + num
        int target = carry+num;
        if(!counts.ContainsKey(target) || counts[target] == 0)
        return false;
        
        result[index++] = num+k;
        counts[num]--;
        counts[target]--;
    }
    
    return true;    
}
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Ask: "Can I sort the array?" — Sorting often enables two-pointer techniques.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• LeetCode provides 4 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: If we fix the value of k, how can we check if an original array exists for the fixed k?

Hint 2: The smallest value of nums is obtained by subtracting k from the smallest value of the original array. How can we use this to reduce the search space for finding a valid k?

Hint 3: You can compute every possible k by using the smallest value of nums (as lower[i]) against every other value in nums (as the corresponding higher[i]).

Hint 4: For every computed k, greedily pair up the values in nums. This can be done sorting nums, then using a map to store previous values and searching that map for a corresponding lower[i] for the current nums[j] (as higher[i]).