LeetCode 1304 - Find N Unique Integers Sum up to Zero

LeetCode Problem 1304

Difficulty: 🟢 Easy
Topics: Array, Math

Solution

Problem Understanding

The problem asks us to construct an array containing exactly n unique integers whose total sum is equal to 0. The keyword any is important here because the problem does not require a specific arrangement or a lexicographically smallest answer. As long as the integers are unique and their sum equals zero, the solution is valid.

The input consists of a single integer n, which represents how many numbers must appear in the resulting array. The output should be a list of n distinct integers. Every value in the array must be different, and if we add all elements together, the result must be exactly 0.

For example, if n = 3, one valid answer is [-1, 0, 1]. These values are unique and sum to zero. If n = 5, we could return [-2, -1, 0, 1, 2], but many other valid answers exist as well.

The constraints tell us that 1 <= n <= 1000. This is a relatively small input size, meaning efficiency is not especially demanding. However, the simplicity of the problem suggests there is likely a direct mathematical construction rather than an expensive search process.

An important observation is that integers naturally cancel each other out in positive and negative pairs. For example, 1 + (-1) = 0, 2 + (-2) = 0, and so on. This immediately suggests a constructive solution.

There are a few important edge cases to consider upfront. When n = 1, the only valid answer is [0], because we need exactly one number and it must sum to zero. When n is even, we can perfectly pair numbers like [-1, 1, -2, 2]. When n is odd, we can use these canceling pairs and include 0 as the middle element. The problem guarantees n >= 1, so we never need to handle invalid inputs such as 0 or negative numbers.

Approaches

Brute Force Approach

A brute-force solution would attempt to generate combinations of unique integers and check whether their sum equals zero. For example, we might repeatedly try random distinct numbers, compute their sum, and verify whether the total becomes zero.

This approach is correct in theory because it explores possible valid arrays until it finds one satisfying the constraints. However, it is highly inefficient. The number of possible combinations grows extremely quickly as n increases, making exhaustive search impractical even for moderate values of n.

Additionally, brute force ignores the mathematical structure of the problem. Since we only need any valid array, there is no reason to search blindly when a direct construction exists.

Optimal Approach, Mathematical Pair Construction

The key insight is that positive and negative pairs naturally cancel out.

For every positive integer x, we can include both x and -x. Their contribution to the total sum is zero:

$$x + (-x) = 0$$

If n is even, we simply generate n / 2 such pairs.

If n is odd, we generate (n - 1) / 2 pairs and include 0. Since adding zero does not change the sum, the overall total remains zero.

This approach guarantees uniqueness because every integer used is distinct. It also guarantees the sum is zero by construction.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(n)	Tries combinations of unique numbers until a valid sum is found
Optimal	O(n)	O(n)	Constructs canceling positive-negative pairs directly

Algorithm Walkthrough

1. Create an empty result array that will store the unique integers.
2. Iterate through integers starting from 1 up to n // 2. For each number i, add both i and -i to the result array. This ensures every added pair contributes a net sum of zero.
3. Check whether n is odd. If it is, append 0 to the result array. This gives us exactly n elements while keeping the total sum unchanged.
4. Return the completed result array.

Why it works

The correctness relies on the invariant that every inserted pair (i, -i) contributes zero to the total sum. Therefore, no matter how many pairs we add, the cumulative sum remains zero. If n is odd, adding 0 preserves the sum while increasing the array size by one. Since every integer value is used only once, uniqueness is guaranteed. Thus, the algorithm always produces exactly n distinct integers summing to zero.

Python Solution

from typing import List

class Solution:
    def sumZero(self, n: int) -> List[int]:
        result = []

        for value in range(1, n // 2 + 1):
            result.append(value)
            result.append(-value)

        if n % 2 == 1:
            result.append(0)

        return result

The implementation starts by creating an empty list called result. This list will store the integers that sum to zero.

The for loop iterates from 1 through n // 2. For each value, the algorithm appends both the positive and negative versions of the number. Since each pair cancels out, the running sum always remains zero.

After generating all pairs, the implementation checks whether n is odd using n % 2 == 1. If true, it appends 0. This ensures the final list contains exactly n elements while preserving the sum requirement.

Finally, the completed list is returned.

Go Solution

func sumZero(n int) []int {
	result := make([]int, 0, n)

	for value := 1; value <= n/2; value++ {
		result = append(result, value)
		result = append(result, -value)
	}

	if n%2 == 1 {
		result = append(result, 0)
	}

	return result
}

The Go implementation closely mirrors the Python solution. A slice named result is created with capacity n to avoid unnecessary reallocations during appends.

The loop generates positive-negative pairs exactly as in Python. If n is odd, 0 is appended to complete the required number of elements.

Unlike Python lists, Go slices benefit from preallocated capacity using make([]int, 0, n), which can slightly improve efficiency. Integer overflow is not a concern here because n <= 1000, and the generated values remain very small.

Worked Examples

Example 1: n = 5

Since 5 is odd, we generate pairs and include 0.

Step	Current Value	Action	Result Array
Start	-	Initialize array	[]
1	1	Add 1 and -1	[1, -1]
2	2	Add 2 and -2	[1, -1, 2, -2]
3	Odd n	Add 0	[1, -1, 2, -2, 0]

Final sum:

$$1 + (-1) + 2 + (-2) + 0 = 0$$

The answer contains exactly 5 unique integers.

Example 2: n = 3

Since 3 is odd, we generate one pair and add 0.

Step	Current Value	Action	Result Array
Start	-	Initialize array	[]
1	1	Add 1 and -1	[1, -1]
2	Odd n	Add 0	[1, -1, 0]

Final sum:

$$1 + (-1) + 0 = 0$$

Example 3: n = 1

Since 1 // 2 = 0, no pairs are generated.

Step	Current Value	Action	Result Array
Start	-	Initialize array	[]
1	Odd n	Add 0	[0]

Final sum:

$$0 = 0$$

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate through approximately n / 2 numbers and perform constant-time operations for each
Space	O(n)	The output array stores exactly n integers

The algorithm runs in linear time because we generate each required element exactly once. The space complexity is also linear because the result array must contain n integers, which is unavoidable since returning the array itself requires O(n) storage.

Test Cases

def validate_result(result, n):
    assert len(result) == n
    assert len(set(result)) == n
    assert sum(result) == 0

solution = Solution()

# Provided examples
validate_result(solution.sumZero(5), 5)  # odd n
validate_result(solution.sumZero(3), 3)  # small odd n
validate_result(solution.sumZero(1), 1)  # minimum boundary

# Even values
validate_result(solution.sumZero(2), 2)  # smallest even n
validate_result(solution.sumZero(4), 4)  # typical even case
validate_result(solution.sumZero(10), 10)  # larger even case

# Odd values
validate_result(solution.sumZero(7), 7)  # typical odd case
validate_result(solution.sumZero(9), 9)  # larger odd case

# Maximum boundary
validate_result(solution.sumZero(1000), 1000)  # largest valid input

# Stress and uniqueness check
result = solution.sumZero(999)
assert len(result) == len(set(result))  # ensure all unique
assert sum(result) == 0  # verify total sum

Test	Why
n = 1	Validates the smallest possible input
n = 2	Verifies smallest even-number case
n = 3	Confirms odd handling with 0
n = 5	Matches provided example structure
n = 10	Tests a larger even input
n = 999	Verifies uniqueness and sum for large odd input
n = 1000	Confirms maximum constraint handling

Edge Cases

n = 1

This is the smallest valid input and can easily break a naive implementation. If the algorithm only generated positive-negative pairs, it would return an empty array because there are no pairs to generate. The implementation handles this correctly by detecting odd n and appending 0, resulting in [0].

Even n

When n is even, no extra element should be added. A buggy implementation might accidentally include 0, producing too many elements. The current solution avoids this by only appending 0 when n % 2 == 1.

Odd n

For odd values of n, positive-negative pairs alone are insufficient because they always produce an even number of elements. The implementation correctly solves this by adding 0, which increases the count by one without changing the sum.

Maximum Constraint, n = 1000

Although 1000 is not very large, it still tests whether the algorithm scales efficiently. A brute-force search would become increasingly impractical as n grows. The mathematical construction handles this efficiently in linear time, generating the answer almost instantly.