LeetCode 1822 - Sign of the Product of an Array

The problem asks us to determine the sign of the product of all numbers in an integer array, without necessarily computing the actual product itself.

leetcodeeasyarraymath

LeetCode Problem 1822

Difficulty: 🟢 Easy
Topics: Array, Math

Solution

Problem Understanding

The problem asks us to determine the sign of the product of all numbers in an integer array, without necessarily computing the actual product itself.

A helper function signFunc(x) is defined as:

  • Return 1 if x > 0
  • Return -1 if x < 0
  • Return 0 if x == 0

We are given an array nums, and we conceptually multiply all its elements together to form a value called product. Our task is to return the sign of that product.

For example:

  • If the array contains an even number of negative values and no zeroes, the final product is positive, so the answer is 1.
  • If the array contains an odd number of negative values and no zeroes, the final product is negative, so the answer is -1.
  • If any value is 0, the entire product becomes 0, so the answer is 0.

The constraints are small:

  • 1 <= nums.length <= 1000
  • -100 <= nums[i] <= 100

Although the values themselves are not large, repeatedly multiplying numbers together could still create very large products in other languages or scenarios. More importantly, the problem only asks for the sign, not the actual product value. This observation leads directly to a more efficient and cleaner solution.

Some important edge cases include:

  • Arrays containing a zero, because the answer immediately becomes 0
  • Arrays with exactly one negative number
  • Arrays with many negative numbers, where parity matters
  • Arrays of length 1
  • Arrays containing only positive values

The problem guarantees that the array is non-empty, so we never need to handle an empty input.

Approaches

Brute Force Approach

The most straightforward approach is to compute the actual product of all numbers in the array and then determine its sign at the end.

We initialize a variable product = 1 and multiply every element into it. After processing the array:

  • If product > 0, return 1
  • If product < 0, return -1
  • Otherwise return 0

This works because multiplication preserves the correct mathematical result.

However, this approach is not ideal. Even though the constraints in this problem are small enough to avoid overflow in Python, other languages may overflow when multiplying many integers together. More importantly, computing the entire product is unnecessary because only the sign matters.

Optimal Approach

The key observation is that we never need the actual product value.

The sign of a product depends only on two things:

  • Whether any number is zero
  • Whether the count of negative numbers is odd or even

The rules are:

  • If any element is 0, the answer is immediately 0
  • Every negative number flips the sign
  • An even number of negative values produces a positive result
  • An odd number of negative values produces a negative result

Instead of computing the product, we can simply track the current sign.

We initialize sign = 1.

For each number:

  • If the number is 0, return 0
  • If the number is negative, multiply sign by -1
  • Otherwise do nothing

At the end, return sign.

This avoids unnecessary multiplication and keeps the logic extremely simple.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(1) Computes the full product directly
Optimal O(n) O(1) Tracks only the sign using negative count parity

Algorithm Walkthrough

  1. Initialize a variable sign = 1.

This variable represents the sign of the product seen so far. We start with positive because multiplying by 1 does not change anything. 2. Iterate through every number in the array.

We process each element one at a time to determine how it affects the final sign. 3. If the current number is 0, immediately return 0.

Any product containing zero becomes zero, so we can stop early without processing the remaining elements. 4. If the current number is negative, flip the sign.

A negative number changes a positive product into a negative one, or vice versa. We can implement this by multiplying sign by -1. 5. If the current number is positive, do nothing.

Positive numbers do not change the sign of the product. 6. After processing all elements, return sign.

At this point, sign correctly represents whether the total product is positive or negative.

Why it works

The algorithm works because the sign of multiplication follows simple mathematical rules:

  • Multiplying by a positive number preserves the current sign
  • Multiplying by a negative number flips the sign
  • Multiplying by zero makes the entire product zero

By tracking only these sign changes, we obtain exactly the same result as computing the full product, while avoiding unnecessary arithmetic.

Python Solution

from typing import List

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

The implementation begins by initializing sign to 1, representing a positive product.

We then iterate through each value in nums.

If a value is 0, we immediately return 0 because the final product must be zero regardless of the remaining elements.

If a value is negative, we multiply sign by -1. This flips the sign each time we encounter a negative number.

Positive numbers are ignored because they do not affect the sign.

After the loop finishes, sign contains the correct answer and is returned.

Go Solution

func arraySign(nums []int) int {
	sign := 1

	for _, num := range nums {
		if num == 0 {
			return 0
		}

		if num < 0 {
			sign *= -1
		}
	}

	return sign
}

The Go implementation follows the exact same logic as the Python version.

One notable difference is that Go uses a range loop to iterate through the slice. Since we never compute the actual product, integer overflow is not a concern.

The problem guarantees that the input slice contains at least one element, so no special handling for empty slices is necessary.

Worked Examples

Example 1

Input:

nums = [-1,-2,-3,-4,3,2,1]

Initial state:

sign = 1
Current Number Action sign
-1 Negative, flip sign -1
-2 Negative, flip sign 1
-3 Negative, flip sign -1
-4 Negative, flip sign 1
3 Positive, no change 1
2 Positive, no change 1
1 Positive, no change 1

Final answer:

1

Example 2

Input:

nums = [1,5,0,2,-3]

Initial state:

sign = 1
Current Number Action sign
1 Positive, no change 1
5 Positive, no change 1
0 Return immediately 0

Final answer:

0

Example 3

Input:

nums = [-1,1,-1,1,-1]

Initial state:

sign = 1
Current Number Action sign
-1 Negative, flip sign -1
1 Positive, no change -1
-1 Negative, flip sign 1
1 Positive, no change 1
-1 Negative, flip sign -1

Final answer:

-1

Complexity Analysis

Measure Complexity Explanation
Time O(n) We scan the array once
Space O(1) Only a single variable is used

The algorithm performs one pass through the array, so the runtime grows linearly with the number of elements.

The memory usage remains constant because we only store the sign variable and do not allocate any extra data structures.

Test Cases

from typing import List

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

sol = Solution()

assert sol.arraySign([-1, -2, -3, -4, 3, 2, 1]) == 1  # even negatives
assert sol.arraySign([1, 5, 0, 2, -3]) == 0  # contains zero
assert sol.arraySign([-1, 1, -1, 1, -1]) == -1  # odd negatives

assert sol.arraySign([5]) == 1  # single positive
assert sol.arraySign([-5]) == -1  # single negative
assert sol.arraySign([0]) == 0  # single zero

assert sol.arraySign([1, 2, 3, 4]) == 1  # all positive
assert sol.arraySign([-1, -2, -3, -4]) == 1  # even count negatives
assert sol.arraySign([-1, -2, -3]) == -1  # odd count negatives

assert sol.arraySign([100, -100, 100, -100]) == 1  # alternating signs
assert sol.arraySign([1, 2, 3, 0, 4, 5]) == 0  # zero in middle
assert sol.arraySign([-1] * 999) == -1  # large odd negative count
assert sol.arraySign([-1] * 1000) == 1  # large even negative count
Test Why
[-1, -2, -3, -4, 3, 2, 1] Validates even number of negatives
[1, 5, 0, 2, -3] Validates early zero detection
[-1, 1, -1, 1, -1] Validates odd negatives
[5] Smallest positive input
[-5] Smallest negative input
[0] Single zero case
[1, 2, 3, 4] All positive numbers
[-1, -2, -3, -4] Even negative count gives positive
[-1, -2, -3] Odd negative count gives negative
[100, -100, 100, -100] Mixed positive and negative values
[1, 2, 3, 0, 4, 5] Zero appearing mid-array
[-1] * 999 Large odd count stress test
[-1] * 1000 Large even count stress test

Edge Cases

A very important edge case is when the array contains a zero. A naive implementation that continues multiplying values unnecessarily may still work, but recognizing zero early allows the algorithm to terminate immediately. In this implementation, the moment a 0 is encountered, the function returns 0.

Another important case is an odd number of negative values. Since each negative flips the sign, forgetting to track parity correctly can produce the wrong result. The implementation handles this cleanly by multiplying the sign variable by -1 every time a negative value appears.

Arrays of length one are also important. The array may contain a single positive number, a single negative number, or zero. Since the algorithm processes each element independently and directly applies the sign rules, these smallest possible inputs are handled naturally without any special-case logic.