LeetCode 2122 - Recover the Original Array

The problem presents a scenario in which Alice has an original array arr of length n consisting of positive integers. She chooses a positive integer k and generates two new arrays: lower and higher.

leetcodehardarrayhash-tabletwo-pointerssortingenumeration

LeetCode Problem 2122

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Two Pointers, Sorting, Enumeration

Solution

Problem Understanding

The problem presents a scenario in which Alice has an original array arr of length n consisting of positive integers. She chooses a positive integer k and generates two new arrays: lower and higher. The array lower is formed by subtracting k from each element of arr, while higher is formed by adding k to each element. The arrays are then merged into a single array nums of length 2n, where the distinction between lower and higher is lost. Our task is to recover the original array arr.

The input is a list of 2n integers representing the union of lower and higher arrays. The expected output is any valid array arr of length n that could have produced nums via some positive integer k. The constraints guarantee that 1 <= n <= 1000 and 1 <= nums[i] <= 10^9, ensuring the solution must handle moderately large arrays efficiently. The problem guarantees at least one valid solution exists, which simplifies considerations of impossibility or empty outputs.

Important edge cases include small arrays (n = 1), arrays where all numbers are equal, arrays with very large gaps (requiring a large k), and arrays with duplicates, which could mislead naive pairing logic.

Approaches

A brute-force approach would attempt all possible pairs of numbers in nums to compute potential values of k and then verify if dividing nums into lower and higher arrays based on that k reconstructs a valid arr. While this would work for small inputs, it is infeasible for n = 1000 since there are O(n^2) possible pairs, and checking each one is O(n), resulting in O(n^3) complexity.

The optimal approach relies on two key observations. First, after sorting nums, the difference between any smaller number and a larger number in nums is 2k if they correspond to the same original element. Second, once we guess a valid k from the sorted array, we can attempt to reconstruct the original array by pairing numbers greedily: always pair the smallest unused number with a number 2k larger in the multiset. This ensures that we correctly recover arr without needing to try all permutations.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(n) Test all pairs for k and validate reconstruction
Optimal O(n^2) O(n) Sort array and attempt valid k from pair differences, use multiset for pairing

Algorithm Walkthrough

  1. Sort nums in ascending order. Sorting ensures we can consider smallest numbers first and attempt to pair them with potential partners based on 2k.
  2. Initialize a multiset (Counter in Python) to track the count of each number in nums.
  3. Iterate over all potential candidates for the smallest element in higher minus the smallest element in nums. Specifically, for each nums[i] > nums[0], compute 2k = nums[i] - nums[0]. Ignore zero or negative differences.
  4. If 2k is even, compute k = (nums[i] - nums[0]) // 2.
  5. Try to reconstruct arr using the computed k:
  • Make a copy of the multiset of numbers.
  • For each number in sorted nums, if it exists in the multiset, consider it as lower[i] = x - k and pair it with higher[i] = x + k. Check if the paired number exists in the multiset. If yes, decrement counts in the multiset and add lower[i] + k to the original array.
  1. If all numbers are successfully paired, return the reconstructed array arr.
  2. If no valid pairing exists for a candidate k, continue to the next candidate.

Why it works: The key invariant is that each original number arr[i] corresponds to exactly two numbers in nums: arr[i] - k and arr[i] + k. By iterating over potential k values derived from differences of the smallest element, we ensure all valid possibilities are tested efficiently. Using a multiset ensures we correctly handle duplicates.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def recoverArray(self, nums: List[int]) -> List[int]:
        nums.sort()
        n = len(nums) // 2
        
        for i in range(1, len(nums)):
            diff = nums[i] - nums[0]
            if diff % 2 != 0 or diff == 0:
                continue
            k = diff // 2
            counter = Counter(nums)
            res = []
            valid = True
            
            for num in nums:
                if counter[num] == 0:
                    continue
                if counter[num + 2 * k] == 0:
                    valid = False
                    break
                counter[num] -= 1
                counter[num + 2 * k] -= 1
                res.append(num + k)
            
            if valid and len(res) == n:
                return res
        
        return []

In this implementation, nums is sorted first. We iterate over potential differences with the smallest element to determine possible k values. A Counter tracks the remaining numbers to pair. For each valid pairing, we append num + k to res and decrement counts. Once a valid array of length n is constructed, it is returned.

Go Solution

package main

import (
    "sort"
)

func recoverArray(nums []int) []int {
    sort.Ints(nums)
    n := len(nums) / 2

    for i := 1; i < len(nums); i++ {
        diff := nums[i] - nums[0]
        if diff == 0 || diff%2 != 0 {
            continue
        }
        k := diff / 2
        counter := make(map[int]int)
        for _, num := range nums {
            counter[num]++
        }
        res := make([]int, 0, n)
        valid := true

        for _, num := range nums {
            if counter[num] == 0 {
                continue
            }
            if counter[num + 2*k] == 0 {
                valid = false
                break
            }
            counter[num]--
            counter[num + 2*k]--
            res = append(res, num + k)
        }

        if valid && len(res) == n {
            return res
        }
    }

    return []int{}
}

In Go, a map is used to simulate the multiset. Sorting and difference calculation is identical to the Python version. The solution ensures proper handling of duplicates and maintains O(n^2) complexity.

Worked Examples

Example 1: nums = [2,10,6,4,8,12]

  • Sort: [2, 4, 6, 8, 10, 12]
  • Smallest number: 2
  • Differences with 2: 2, 4, 6, 8, 10
  • Candidate k: 1, 2, 3, 4, 5
  • k = 1 yields pairs: (2,4), (6,8), (10,12)
  • Original array: [3, 7, 11]

Example 2: nums = [1,1,3,3]

  • Sort: [1,1,3,3]
  • Smallest number: 1
  • Differences with 1: 0, 2, 2
  • k = 1 yields pairs: (1,3), (1,3)
  • Original array: [2,2]

Example 3: nums = [5,435]

  • Sort: [5,435]
  • Smallest number: 5
  • Difference with 5: 430
  • k = 215
  • Original array: [220]

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Sorting is O(n log n), then O(n) candidate k values each with O(n) pairing
Space O(n) Counter/multiset uses O(n) space to track numbers

The time complexity is acceptable given the constraints (n <= 1000). Sorting dominates initially, and pairing is efficient due to the multiset.

Test Cases

# Provided examples
assert Solution().recoverArray([2,10,6,4,8,12]) in [[3,7,11],[5,7,9]] # multiple valid
assert Solution().recoverArray([1,1,3,3]) == [2,2]
assert Solution().recoverArray([5,435]) == [220]

# Edge cases
assert Solution().recoverArray([1,3]) == [2] # minimal array
assert Solution().recoverArray([1,1,1,1]) == [1,1] # all identical
assert Solution().recoverArray([1,1000000000]) == [500000001] # extreme difference
Test Why
[2,10,6,4,8,12] Multiple valid arrays; checks general pairing logic
[1,1,3,3] Duplicate numbers;