Problem Overview
LeetCode 1822 Sign of the Product of an Array asks you to return the sign of the product of all elements in an integer array. The return value is 1 if the product is positive, -1 if the product is negative, and 0 if the product is zero.
The key constraint is that you must not actually compute the product. The array can have up to 1000 elements each as large as 10^9 in absolute value — multiplying them all would create a number too large for any standard integer type.
This is a pure math reasoning problem. The sign of a product follows well-known rules: a product is zero if any factor is zero, negative if an odd number of factors are negative, and positive if all factors are non-zero and an even number are negative.
- Return 1 if the product of all elements is positive
- Return -1 if the product of all elements is negative
- Return 0 if any element is zero (product is zero)
- Do NOT compute the actual product — it overflows standard integer types
- Array length up to 1000, elements up to 10^9 in absolute value
Count Negatives
The approach is straightforward: scan the array once. If you encounter any element equal to zero, the entire product is zero — return 0 immediately. Otherwise, count how many elements are strictly negative.
After scanning the full array, check the negative count. If it is even, the product is positive — return 1. If it is odd, the product is negative — return -1. Two negatives multiply to a positive; three negatives multiply to a negative; and so on.
This approach is O(n) time and O(1) space. You never need to store the partial product or use big-integer arithmetic. Counting is safe even for the largest possible inputs.
Never Compute the Actual Product
With numbers up to 10^9 and n up to 1000, the product overflows any integer type — even 64-bit. Count negatives instead: even count means positive product (+1), odd count means negative product (-1).
Algorithm
The algorithm distills to a single pass over the array with two early-exit / accumulation rules. It is concise enough to write in an interview in under two minutes once the insight clicks.
The zero check must come before the negative check in the loop body. A zero element collapses the entire product to zero regardless of how many negatives exist — the early return prevents unnecessary counting.
After the loop, the parity of the negative count completely determines the answer. The modulo operation (negativeCount % 2) elegantly converts the count into a sign: 0 maps to positive (+1), 1 maps to negative (-1).
- 1Initialize negativeCount = 0
- 2For each num in the array:
- 3 If num == 0, return 0 immediately
- 4 If num < 0, increment negativeCount
- 5After the loop: return negativeCount % 2 == 0 ? 1 : -1
Sign Multiplication Alternative
An equivalent approach is to track a running sign variable instead of counting negatives. Initialize sign = 1. For each element: if it is zero, return 0 immediately; if it is negative, flip the sign by multiplying by -1. Return the sign at the end.
This "sign flip" formulation mirrors how multiplication actually works with signs. Each negative factor flips the product from positive to negative or vice versa. The accumulated sign variable holds the answer without any division or modulo arithmetic.
Both approaches — counting negatives and sign flipping — produce identical results and have identical O(n) time and O(1) space complexity. The sign flip version is often easier to explain verbally in an interview because it directly models the math.
Sign Flip is Equivalent to Counting Negatives
The sign-flip approach (sign *= -1 for each negative) is mathematically identical to counting negatives: each negative toggles the parity. The final sign value is the answer without any counting or modulo — pick whichever reads more clearly to you.
Walk-Through Example
Consider the input array [-1, -2, -3, -4, 3, 2, 1]. Walk through each element: -1 is negative (count=1), -2 is negative (count=2), -3 is negative (count=3), -4 is negative (count=4), 3 is positive (count stays 4), 2 is positive (count stays 4), 1 is positive (count stays 4).
No element is zero so we never return early. The final negativeCount is 4, which is even (4 % 2 == 0), so the function returns 1 — indicating a positive product.
Verification: the actual product is (-1) * (-2) * (-3) * (-4) * 3 * 2 * 1 = 2 * (-3) * (-4) * 6 = (-6) * (-4) * 6 = 24 * 6 = 144. The product is 144, which is indeed positive — confirming our answer of 1.
- 1Array: [-1, -2, -3, -4, 3, 2, 1]
- 2Check for zeros: none found
- 3Count negatives: -1, -2, -3, -4 → negativeCount = 4
- 44 % 2 == 0, so the product sign is positive
- 5Return 1
- 6Verify: actual product = 144 (positive) ✓
Code Walkthrough — Python and Java
The sign-flip version translates cleanly into Python: initialize sign = 1, loop over nums, return 0 if num == 0, multiply sign by -1 if num < 0, then return sign. Four lines of logic inside the function body. O(n) time, O(1) space.
In Java the pattern is identical. Use an int sign = 1, loop with a for-each, check zero first, then flip on negative, return sign. The function signature is public int arraySign(int[] nums). No casting or overflow concerns since you never multiply the actual numbers.
Both implementations have the same structure: guard on zero, mutate sign on negative, return sign. The zero check MUST come before the sign flip — if you check sign first and num happens to be both zero-valued and somehow flagged negative (impossible in this problem but good habit), you avoid confusion by always returning 0 for zeros unconditionally.
Check for Zero FIRST
Always check if num == 0 before checking if num < 0. A zero element makes the entire product zero regardless of how many negatives exist. Placing the zero check first also enables an early return that skips all remaining work.