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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Recover the Original Array

Number: 2241

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Alice originally had an array arr of n positive integers. She selected a positive integer k and built two arrays: lower where lower[i] = arr[i] - k and higher where higher[i] = arr[i] + k. The 2n numbers obtained by merging these two arrays (in arbitrary order) are given in nums. The task is to recover any valid original array arr. Note that k must be positive, so the pairing must enforce that the difference between the paired numbers is positive and even.

Key Insights

  • Because lower[i] = arr[i] - k and higher[i] = arr[i] + k, each pair of corresponding numbers differs by exactly 2*k.
  • In the merged array, the smallest number must come from the lower array.
  • For the smallest number low, any candidate x with x > low that makes (x - low) even is a potential partner to determine k.
  • Once k is chosen (k = (x - low)/2), every lower value x must have a matching x + 2*k.
  • A greedy pairing using a frequency map (or multiset) on the sorted nums can verify candidate k and help recover arr.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting, where n is the number of elements in the original arr. Space Complexity: O(n) for the frequency map and for storing the result.

Solution

The algorithm starts by sorting nums. Since lower elements are always smaller than their corresponding higher elements (by exactly 2k), the smallest number in nums must be part of the lower array. For every candidate number in nums (other than the smallest), if the difference with the smallest number is even and positive, we compute a candidate k as (candidate - smallest)/2. We then try to pair every remaining number. Using a frequency map, we repeatedly take the smallest available number as a potential lower element and check if its corresponding higher element (i.e. lower + 2k) exists in the map. If all numbers can be successfully paired, we compute the original number as lower + k and add it to the answer. If pairing fails at any point, we move to the next candidate for k. This greedy approach assures correctness because the problem guarantees at least one valid answer exists.

Code Solutions

# Python solution with detailed comments
from collections import Counter

def recoverArray(nums):
    # sort the input array to ensure the smallest element is at the front
    nums.sort()
    n = len(nums) // 2

    # The smallest element must come from 'lower' array.
    # Try to find a valid candidate k using a candidate pair (smallest, candidate)
    for i in range(1, len(nums)):
        diff = nums[i] - nums[0]
        # k must be positive and an integer, so diff must be even and > 0.
        if diff <= 0 or diff % 2 != 0:
            continue
        k = diff // 2
        freq = Counter(nums)  # frequency map of all numbers
        cur_arr = []  # this will store the recovered original array

        valid = True
        # iterate over the sorted numbers
        for num in nums:
            if freq[num] == 0:
                # already paired, skip
                continue
            # This number acts as candidate lower value.
            # Decrement its frequency as we decide to pair it
            freq[num] -= 1
            # The corresponding higher value should be num + 2*k.
            target = num + 2 * k
            if freq[target] <= 0:
                valid = False
                break
            # Pair found: decrement the frequency of the higher number.
            freq[target] -= 1
            # The original number is recovered as lower + k.
            cur_arr.append(num + k)
        if valid and len(cur_arr) == n:
            return cur_arr
    return []  # Given constraints, this return should not be reached.

# Example usage:
print(recoverArray([2,10,6,4,8,12]))  # Expected: a valid instance, e.g., [3,7,11]
← Back to All Questions