Find N Unique Integers Sum up to Zero

Problem

Qn - Find N Unique Integers Sum up to Zero

Approach

Initially thought that I needed to do some form of random picking of numbers, while maintaining a curr_sum, but I forgot that the elements need to be unique. The first idea is to convert the array into a set and when we generate a random number, we check if it’s inside the set. But what if we keep generating numbers and its always in the set, that’s not good too.

I then thought, what’s stopping me from just making all the elements in the array deterministic? We can just use the element indexes as values, then at the end just set whatever number to make the sum 0. Well, that works. But I forgot that there is an edge case I did not consider, where n=2 and we set the first element to be 0 and the last element would also be 0, making it fail the uniqueness check. To tackle that we can just start from 1

Complexity

• Time: $O(n)$
• Space: $O(1)$

Code

class Solution:
    def sumZero(self, n: int) -> List[int]:
        curr_sum = 0
        res = []
        for num in range(1, n):
            curr_sum += num
            res.append(num)
 
        return res + [-curr_sum]