Abstract / Summary

Given a sorted list of unique integers where each element is the sum of two original numbers, find the original array of unique numbers.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 42% (30k+ submissions).

Typical patterns to solve this problem:

• Array
• Enumeration
• Hash Table
• Sorting
• Two Pointers

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a Solution class with a single method recoverArray. The method receives a list of integers, nums, and attempts to reconstruct an original array whose pairwise sums (or a related transformation) correspond to the input. The algorithm proceeds in three logical phases: preparation through sorting, identification of a valid offset k, and reconstruction of the target array using the discovered offset.

Preparation and Sorting

The first operation determines the length of the input and sorts it in non-decreasing order. Sorting enables binary search operations later in the algorithm and guarantees that the smallest elements are examined first, which is crucial for the candidate generation logic.

size = len(nums)
nums.sort()

By sorting, the code ensures that any subsequent search for a matching counterpart of a value can rely on the ordered nature of the list, allowing the use of bisect_left for efficient look-ups.

Candidate Offset Discovery

The core of the method searches for a suitable difference delta between two elements that can serve as twice the desired offset k. Two nested loops iterate over pairs of indices (i, j). The inner loop computes delta = nums[j] - nums[i]. If delta is odd, the pair is discarded because a valid offset must be an integer after halving.

for i in range(size):
    if k:
        break
    for j in range(i + 1, size):
        delta = nums[j] - nums[i]
        if delta % 2 == 1:
            continue
        # validation logic follows

The algorithm then creates a copy of the sorted list, have, and attempts to pair each non-zero element with another element exactly delta larger. This pairing is performed using bisect_left, which locates the required counterpart in logarithmic time. If a counterpart cannot be found, the inner validation loop aborts early, and the algorithm proceeds to the next candidate pair.

have = nums.copy()
for i in range(len(have)):
    if have[i] == 0:
        continue
    pos = bisect_left(have, have[i] + delta, i + 1)
    if pos == len(have) or have[pos] != have[i] + delta:
        break
    have[i] = have[pos] = 0

When every element can be successfully paired, the sum of have becomes zero, indicating that the current delta yields a consistent pairing across the entire list. At that point, k is set to delta // 2, and the search terminates.

if sum(have) == 0:
    k = delta // 2
    break

The early termination conditions (if k: break) and the immediate break upon a successful pairing reduce unnecessary iterations, preventing the algorithm from exhaustively testing all possible pairs once a valid offset is found.

Reconstruction of the Result Array

With a valid offset k identified, the method proceeds to rebuild the original array. It again works on a fresh copy of the sorted input, have. For each non-zero entry, it locates the element that is exactly 2 * k larger, marks both as used by setting them to zero, and appends the midpoint (have[i] + k) to the result list.

result = []
have = nums.copy()
for i in range(len(have)):
    if have[i] == 0:
        continue
    pos = bisect_left(have, have[i] + 2*k, i + 1)
    have[pos] = 0
    result.append(have[i] + k)

The use of bisect_left again provides a fast lookup for the counterpart element, ensuring that each pairing operation runs in logarithmic time relative to the current list size. By marking used elements with zero, the algorithm avoids revisiting already paired values without needing an auxiliary data structure.

Edge Cases Handled

The implementation explicitly skips pairs where the computed delta is odd, thereby handling the scenario where an integer offset cannot exist. Zero entries in the working copy have are ignored throughout both the validation and reconstruction phases, which gracefully manages cases where duplicate values or previously paired elements appear later in the list. The binary search bounds (i + 1) guarantee that the algorithm never pairs an element with itself, protecting against self-matching edge cases. Additionally, the early break when a pairing fails prevents the algorithm from proceeding with an invalid candidate, ensuring correctness even when the input contains values that cannot be paired under the current delta.

Performance Optimizations Observed

Sorting the input once at the beginning establishes an ordered structure that enables binary search, reducing the cost of locating counterpart elements from linear to logarithmic time. The repeated use of bisect_left leverages this ordering throughout both the candidate discovery and reconstruction phases. Early exit strategies-such as breaking out of loops once a valid k is found or aborting the pairing process as soon as a mismatch is detected-prevent unnecessary work, especially on large inputs where many candidate pairs would otherwise be examined. The in-place marking of used elements with zero eliminates the need for additional bookkeeping structures, conserving memory and simplifying the pairing logic. By copying the original list only when necessary, the code avoids repeated deep copies, further contributing to efficient resource usage.

Imagine you have a big bucket full of mixed-up number tiles. Every number in that bucket actually came from a secret pair where one number was a little bit smaller and one was a little bit bigger. The game is to find the secret difference between those pairs so you can put all the numbers back into their original groups.

First, the code lines up all the tiles from smallest to biggest like a parade. Then, it starts picking two tiles at a time to guess how far apart they might be. If it finds a gap that works, it tests that gap across the whole collection to see if every single tile can find its matching partner.

Once the correct gap is found, the code goes through the parade one more time. It grabs the small tile, adds the secret amount to it to find its partner, and sets both aside so they do not get picked again. It saves the middle point of those pairs to track all the original numbers. It is just like solving a puzzle where you match every small piece with a partner to see the full picture underneath.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: polynomial
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Python	Java			TS
	WalkCCC	C++		Python	Java
	leetcode.ca	C++		Python	Java		Go
	Progiez	C++		Python	Java
github	black-shadows	C++
	charles-wangkai				Java
	everthis		JS
	fsq	C++
	JoshCrozier		JS
	lkwq007			Python
	suxrobGM					C#
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality