Sign of the Product of an Array

How it works

Instead of counting negatives and checking parity at the end, we can track the running sign directly. Start with a sign of 1 (positive). Each time we encounter a negative number, we flip the sign by multiplying by -1. If we encounter zero, the product is immediately 0. This approach mirrors the actual multiplication process but only tracks the sign.

Steps

1. Initialize sign = 1.
2. Iterate through each number in the array:
   • If the number is 0, return 0 immediately.
   • If the number is negative, flip the sign: sign *= -1.
3. Return sign.

Complexity

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

Things to watch for

Not Handling Zero as a Special Case

If any element in the array is zero, the entire product is zero, and the function should immediately return 0. A common mistake is forgetting to check for zeros and only focusing on counting or tracking negative numbers, which leads to returning 1 or -1 when the answer should be 0.

Computing the Actual Product

Attempting to calculate the actual product of all elements is unnecessary and dangerous. For large arrays or large values, the product can overflow even 64-bit integers, causing undefined behavior or incorrect results. The problem only asks for the sign, so you should track sign changes without computing the full product.

class Solution:
    def arraySign(self, nums: list[int]) -> int:
        sign = 1
        for num in nums:
            if num == 0:
                return 0
            if num < 0:
                sign *= -1
        return sign

class Solution {
public:
    int arraySign(vector<int>& nums) {
        int sign = 1;
        for (int num : nums) {
            if (num == 0) {
                return 0;
            }
            if (num < 0) {
                sign *= -1;
            }
        }
        return sign;
    }
};