Scale Engineer

Find N Unique Integers Sum up to Zero

Easy
#1214Time: O(n) - We iterate once through the first `n-1` elements of the array to populate them. This is a single loop that runs `n-1` times, resulting in a linear time complexity.Space: O(n) or O(1) - We need an array of size `n` to store and return the result. If the space for the output array is considered, the complexity is O(n). If not, the extra space used is O(1) for the sum variable.
Patterns
Math
Data structures
Array

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves building the array by adding n-1 unique integers and then calculating the final integer needed to make the sum of the array zero. For instance, we can add the integers 1, 2, ..., n-1.

Algorithm

  • Create an integer array result of size n.
  • Initialize a variable currentSum to 0.
  • Iterate from i = 0 to n-2:
    • Set result[i] = i + 1.
    • Add i + 1 to currentSum.
  • Set the last element of the array, result[n-1], to -currentSum.
  • Return the result array.

Walkthrough

The core idea is to fill the first n-1 positions of the result array with simple, unique integers. A straightforward choice is to use the sequence 1, 2, 3, ..., n-1. While filling the array, we keep track of the sum of these numbers. After placing n-1 numbers, the sum will be S = 1 + 2 + ... + (n-1). To make the total sum of all n integers zero, the last integer must be -S. This guarantees the sum-to-zero property. We also need to ensure all n integers are unique. Since we added positive integers 1 through n-1, the final number -S will be negative (for n > 1) and thus distinct from the others. For the base case n=1, the loop is skipped, the sum is 0, and the result is [0], which is correct.

class Solution {    public int[] sumZero(int n) {        int[] result = new int[n];        int currentSum = 0;        for (int i = 0; i < n - 1; i++) {            result[i] = i + 1;            currentSum += result[i];        }        if (n > 0) { // To handle n=0 case if constraints allowed, though here n>=1            result[n - 1] = -currentSum;        }        return result;    }}

Complexity

Time

O(n) - We iterate once through the first `n-1` elements of the array to populate them. This is a single loop that runs `n-1` times, resulting in a linear time complexity.

Space

O(n) or O(1) - We need an array of size `n` to store and return the result. If the space for the output array is considered, the complexity is O(n). If not, the extra space used is O(1) for the sum variable.

Trade-offs

Pros

  • Conceptually simple and easy to implement.

  • Guaranteed to produce a correct and valid result for any n >= 1.

Cons

  • The magnitude of the last number can be quite large. The sum of the first k integers is k*(k+1)/2. For n=1000, the last number would be -(999*1000)/2 = -499500.

  • Slightly less elegant compared to the symmetric approach.

Solutions

class Solution { public int [] sumZero ( int n ) { int [] ans = new int [ n ]; for ( int i = 1 , j = 0 ; i <= n / 2 ; ++ i ) { ans [ j ++] = i ; ans [ j ++] = - i ; } return ans ; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem