Find N Unique Integers Sum up to Zero - Solution & Explanation
Problem Statement
Given an integer n, return any array containing n unique integers such that they add up to 0.
Example 1:
Input: n = 5 Output: [-7,-1,1,3,4] Explanation: These arrays also are accepted [-5,-1,1,2,3] , [-3,-1,2,-2,4].
Example 2:
Input: n = 3 Output: [-1,0,1]
Example 3:
Input: n = 1 Output: [0]
Constraints:
1 <= n <= 1000
Approach Overview
Problem Overview: You need to construct an array of n unique integers such that their total sum equals zero. The values can be any integers as long as they are distinct and the final sum is exactly 0. Because the order does not matter and many valid answers exist, the goal is simply to generate one correct combination efficiently.
Approach 1: Use Symmetric Pairing (O(n) time, O(n) space)
The simplest observation is that every positive number x cancels out with -x. Using this symmetry, you can construct pairs like (1, -1), (2, -2), and continue until you fill the array. Iterate from 1 to n/2 and append both i and -i to the result array. If n is odd, add a single 0 at the end since zero does not affect the sum and remains unique. The algorithm only requires a single pass to build the result, giving O(n) time complexity and O(n) space for the output array. This method works well because it directly exploits arithmetic symmetry instead of searching for combinations. Problems involving array construction often benefit from such mathematical observations. If you are practicing array manipulation patterns, see more examples under Array problems.
Approach 2: Consecutive Integers Strategy (O(n) time, O(n) space)
Another clean construction uses consecutive integers centered around zero. Generate numbers from -(n/2) up to n/2 while skipping zero when necessary to maintain uniqueness and the correct count. A common implementation builds values from 1 to n-1 and keeps a running sum, then adds the final value as -sum. Because the earlier values are distinct, the last number guarantees the total becomes zero. The loop runs once, so the time complexity is O(n) and the extra space used is O(n). This approach highlights a useful trick in Math-based problems: control the running sum and adjust the final element to satisfy the constraint.
Recommended for interviews: The symmetric pairing method is what most interviewers expect. It shows you immediately recognized the mathematical structure of the problem and produced a clean O(n) construction without unnecessary bookkeeping. The consecutive integer strategy is also valid and demonstrates comfort with array generation and running-sum reasoning. If you mention both approaches during discussion, it signals strong problem-solving depth even for an easy-level question.
Approach 1: Use Symmetric Pairing
This approach involves using numbers in symmetric pairs to achieve the sum of zero. For example, if n is even, you can use pairs like (-1, 1), (-2, 2), etc. If n is odd, include zero to the list to keep the sum zero.
The function first allocates memory for the array and iterates to add pairs of integers, their negatives and zero for an odd n. It uses dynamic memory allocation to return the array.
Complexity
Time Complexity: O(n) because it processes n elements. Space Complexity: O(n) because it returns an array of n elements.
Approach 2: Consecutive Integers Strategy
This approach utilizes consecutive integers starting from 1-n and converting half to negative. The sequence is constructed such that all elements are positive in the first half and their negative counterparts in the second, ensuring zero sum.
The C solution sums numbers and alters the last number to correct the sum to zero. Numbers 1 to n-1 remain positive, with a compensating last element.
Complexity
Time Complexity: O(n). Space Complexity: O(n).
Approach 3: Construction
We can start from 1 and alternately add positive and negative numbers to the result array. We repeat this process \frac{n}{2} times. If n is odd, we add 0 to the result array at the end.
The time complexity is O(n), where n is the given integer. Ignoring the space used for the answer, the space complexity is O(1).
Approach 4: Construction + Mathematics
We can also add all integers from 1 to n-1 to the result array, and finally add the opposite of the sum of the first n-1 integers, which is -\frac{n(n-1)}{2}, to the result array.
The time complexity is O(n), where n is the given integer. Ignoring the space used for the answer, the space complexity is O(1).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Use Symmetric Pairing | Time Complexity: O(n) because it processes n elements. Space Complexity: O(n) because it returns an array of n elements. |
| Consecutive Integers Strategy | Time Complexity: O(n). Space Complexity: O(n). |
| Construction | — |
| Construction + Mathematics | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Symmetric Pairing | O(n) | O(n) | Best general solution. Simple construction using positive and negative pairs. |
| Consecutive Integers Strategy | O(n) | O(n) | Useful when reasoning with running sums or constructing numbers sequentially. |
Video Solution
Find N Unique Integers Sum up to Zero | 2 Easy Ways | Leetcode 1304 | codestorywithMIK • codestorywithMIK • 4,805 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find N Unique Integers Sum up to Zero easy or hard?
Find N Unique Integers Sum up to Zero Python/Java solution
How to solve Find N Unique Integers Sum up to Zero in O(n)?
What is the best approach for Find N Unique Integers Sum up to Zero?
Is Find N Unique Integers Sum up to Zero asked at Google/Amazon/Meta?
What data structure is used in Find N Unique Integers Sum up to Zero?
What is the time complexity of Find N Unique Integers Sum up to Zero?
Ready to solve this problem?
Practice Find N Unique Integers Sum up to Zero with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor