Sign of the Product of an Array
EasyPrompt
Implement a function signFunc(x) that returns:
1ifxis positive.-1ifxis negative.0ifxis equal to0.
You are given an integer array nums. Let product be the product of all values in the array nums.
Return signFunc(product).
Example 1:
Input: nums = [-1,-2,-3,-4,3,2,1]
Output: 1
Explanation: The product of all values in the array is 144, and signFunc(144) = 1Example 2:
Input: nums = [1,5,0,2,-3]
Output: 0
Explanation: The product of all values in the array is 0, and signFunc(0) = 0Example 3:
Input: nums = [-1,1,-1,1,-1]
Output: -1
Explanation: The product of all values in the array is -1, and signFunc(-1) = -1
Constraints:
1 <= nums.length <= 1000-100 <= nums[i] <= 100
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code. It calculates the product of all numbers in the array and then determines the sign of the final product. This method is straightforward but suffers from significant performance and correctness issues due to potential integer overflow.
Algorithm
- Initialize a
BigIntegervariableproducttoBigInteger.ONE. - Iterate through each number in the
numsarray. - In each iteration, multiply the
productby the current number (converted to aBigInteger). - After the loop, use the
signum()method of theBigIntegerclass, which returns -1, 0, or 1 for negative, zero, or positive values, respectively. This directly corresponds to the required output ofsignFunc.
Walkthrough
The core idea is to compute the actual product of all elements in the nums array. Since the product can become extremely large and exceed the limits of standard integer types like int or long, this approach requires a data type that can handle arbitrarily large integers, such as BigInteger in Java.
import java.math.BigInteger; class Solution { public int arraySign(int[] nums) { BigInteger product = BigInteger.ONE; for (int num : nums) { product = product.multiply(BigInteger.valueOf(num)); } return product.signum(); }}Complexity
Time
O(N * M), where N is the length of the array and M is the average number of bits in the intermediate products. `BigInteger` multiplication is not a constant-time operation, making this significantly slower than a simple linear scan.
Space
O(M), where M is the number of bits required to store the final product. This can be substantial for large inputs and product values.
Trade-offs
Pros
Simple to understand as it directly follows the problem's definition.
Cons
Highly inefficient due to the computational overhead of
BigIntegeroperations.Consumes significant memory to store the large intermediate and final product values.
If implemented with primitive types (like
long), it would be incorrect and fail for many inputs due to integer overflow.
This approach avoids calculating the large product altogether. Instead, it focuses only on the sign of the product, which is all that's needed to solve the problem. The sign of a product is determined by the presence of zero or the number of negative factors.
Algorithm
- Initialize a variable,
sign, to1(representing an initial positive sign). - Iterate through each number
numin thenumsarray. - If
numis0, the final product is0. Return0immediately. - If
numis negative, flip the current sign by multiplyingsignby-1. - If
numis positive, do nothing as it does not affect the sign. - After the loop, return the final value of
sign.
Walkthrough
The key insight is that we don't need the value of the product, only its sign. The sign of the product of a series of numbers has two special properties that can be exploited for an efficient solution:
- If any number in the series is zero, the entire product is zero.
- The sign of the product is determined by the parity (even or odd) of the count of negative numbers. An even number of negative factors results in a positive product, while an odd number results in a negative product. Positive factors do not change the sign.
This leads to a simple and fast algorithm:
class Solution { public int arraySign(int[] nums) { int sign = 1; for (int num : nums) { if (num == 0) { return 0; } if (num < 0) { sign = -sign; } } return sign; }}Complexity
Time
O(N), where N is the number of elements in the array. We perform a single pass through the array, and each operation inside the loop is constant time.
Space
O(1). We only use a single extra integer variable to keep track of the sign, regardless of the input size.
Trade-offs
Pros
Extremely efficient in both time and space.
Avoids all overflow issues by not calculating the actual product.
The logic is simple and robust.
Features early exit optimization: it terminates as soon as a zero is encountered.
Cons
Requires a small logical leap from the problem's literal definition of calculating a product.
Solutions
Solution
class Solution {public int arraySign(int[] nums) { int ans = 1; for (int v : nums) { if (v == 0) { return 0; } if (v < 0) { ans *= -1; } } return ans; }}/** * @param {number[]} nums * @return {number} */ var arraySign = function ( nums,) { let ans = 1; for (const v of nums) { if (!v) { return 0; } if (v < 0) { ans *= -1; } } return ans;};class Solution {public: int arraySign(vector<int> &nums) { int ans = 1; for (int v : nums) { if (!v) return 0; if (v < 0) ans *= -1; } return ans; }};class Solution: def arraySign(self, nums: List[int]) -> int: ans = 1 for v in nums: if v == 0: return 0 if v < 0: ans *= - 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.