algoadvance

Leetcode 1304. Find N Unique Integers Sum up to Zero

Problem Statement

Given an integer n, return any array containing n unique integers such that they add up to zero.

Clarifying Questions

  1. Q: Can n be zero or negative? A: Based on typical problem constraints, n should be at least 1. Negative or zero wouldn’t make sense in this context.

  2. Q: Are there any constraints on the range of the integers in the array? A: No specific constraints on the range as long as they are integers.

  3. Q: Should the output array be sorted? A: The problem doesn’t specify sorting, so non-sorted arrays are acceptable as long as they meet the unique and sum-to-zero criteria.

Strategy

To solve this problem, we can leverage the properties of symmetric pairs around zero. Here’s the strategy step-by-step:

  1. If n is even, we can pair positive and negative integers symmetrically, e.g. for n=4, use [-2, -1, 1, 2].
  2. If n is odd, we can do similar pairing but add a zero to ensure the sum is zero, e.g. for n=5, use [-2, -1, 0, 1, 2].

We’ll generate integers from -(n//2) to n//2 and include zero if n is odd. This guarantees the integers are unique and sum to zero.

Code

Here’s the implementation in Java:

class Solution {
    public int[] sumZero(int n) {
        int[] result = new int[n];
        int index = 0;
        
        // If n is odd, include zero in the result
        if (n % 2 == 1) {
            result[index++] = 0;
        }
        
        int halfN = n / 2;
        for (int i = 1; i <= halfN; i++) {
            result[index++] = i;
            result[index++] = -i;
        }
        
        return result;
    }
}

Time Complexity

The time complexity of this solution is O(n), where n is the number of integers in the array. We are simply iterating n times to fill the array, thus making the approach linear in complexity.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI