We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Recover the Original Array

Difficulty: 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:

  1. lower[i] = arr[i] - k, for every index i where 0 <= i < n
  2. 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.

Key Insights

  • The numbers in nums can be split into two groups: those that are lower (arr[i] - k) and those that are higher (arr[i] + k).
  • Each number in nums can be represented as either lower or higher, leading to the equation: arr[i] = (lower[i] + higher[i]) / 2.
  • The sum of the two groups will always equal the sum of the original array, which helps to find k.
  • The problem requires careful pairing of numbers to ensure that the derived array arr contains valid integers.

Space and Time Complexity

Time Complexity: O(n log n) - sorting the nums array takes O(n log n), and subsequent processing takes O(n). Space Complexity: O(n) - for storing the mapped values in a hash table/dictionary.

Solution

To solve this problem, we can follow these steps:

  1. Sort the input array nums.
  2. Use a hash table to store the counts of each number.
  3. Iterate through the sorted nums array and for each number, attempt to form pairs with the next number to retrieve potential values of arr.
  4. Calculate the original value arr[i] using the midpoint formula: (lower + higher) / 2.
  5. Validate the pairs to ensure they correctly account for the original array's construction.

Code Solutions

def recoverArray(nums):
    nums.sort()
    counter = {}
    
    for num in nums:
        counter[num] = counter.get(num, 0) + 1
    
    n = len(nums) // 2
    for k in range(1, 10**9):
        original = []
        temp_counter = counter.copy()
        
        for num in nums:
            if temp_counter.get(num, 0) > 0:
                lower = num
                higher = num + 2 * k
                if temp_counter.get(higher, 0) > 0:
                    original.append((lower + higher) // 2)
                    temp_counter[lower] -= 1
                    temp_counter[higher] -= 1
        
        if len(original) == n:
            return original
    return []
← Back to All Questions