How do you solve Recover the Original Array on LeetCode?

Recover the Original Array (LeetCode #2122) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: The relationship between lower, higher, and the original array arr is crucial to derive k.

What is the time complexity of Recover the Original Array?

The optimal solution for Recover the Original Array runs in O(n log n) time and uses O(n) space. The time complexity is O(n log n) due to sorting the unique elements of nums, and the space complexity is O(n) for storing counts.

What is the brute force solution for Recover the Original Array?

The brute force approach for Recover the Original Array is Brute Force, with O(n²) time complexity and O(1) space complexity. We can try every possible value of k and check if we can form the original array arr. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n log n).

What are the interview tips for Recover the Original Array?

Always start with a simple brute-force approach to understand the problem. Think about how you can reduce the search space for k based on the input. Practice explaining your thought process clearly, as communication is key in interviews.

What are common mistakes when solving Recover the Original Array?

Not considering all possible values of k derived from the smallest elements. Failing to check if lower and higher sets can actually be formed from the counts.

#2122

Recover the Original Array

Hard

ArrayHash TableTwo PointersSortingEnumerationHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

We can use a HashMap to count occurrences of each number and derive k directly from the smallest element. This reduces unnecessary checks.

⚙️

Algorithm

3 steps

1Step 1: Count the occurrences of each number in nums using a HashMap.
2Step 2: Iterate through the unique numbers and calculate potential k values based on the smallest number.
3Step 3: For each k, check if we can form the original array by ensuring that for every lower[i], there exists a higher[i].

solution.py12 lines

1from collections import Counter
2
3def recoverArray(nums):
4    count = Counter(nums)
5    n = len(nums) // 2
6    for num in sorted(count.keys()):
7        k = (count[num] + 1) // 2
8        lower = num - k
9        higher = num + k
10        if count[lower] >= k and count[higher] >= k:
11            return [lower] * k + [higher] * k
12    return []

ℹ

Complexity note: The time complexity is O(n log n) due to sorting the unique elements of nums, and the space complexity is O(n) for storing counts.

1The relationship between lower, higher, and the original array arr is crucial to derive k.
2Sorting the input helps in easily finding pairs and managing counts.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.