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.
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; }}Video 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.