1822. Sign of the Product of an Array
Problem Description
You need to implement a function that determines the sign of the product of all numbers in an array.
The function signFunc(x)
should return:
1
ifx
is positive-1
ifx
is negative0
ifx
equals0
Given an integer array nums
, you need to:
- Calculate the product of all values in the array
- Return the sign of that product using the
signFunc
logic
For example:
- If
nums = [1, 2, 3]
, the product is6
(positive), so return1
- If
nums = [-1, 2, 3]
, the product is-6
(negative), so return-1
- If
nums = [1, 0, 3]
, the product is0
, so return0
The key insight is that you don't actually need to calculate the full product (which could cause overflow). Instead, you only need to track:
- Whether any element is
0
(which makes the entire product0
) - The count of negative numbers (odd count means negative product, even count means positive product)
The solution traverses the array once, immediately returning 0
if any element is 0
, and flipping the sign for each negative number encountered. This efficiently determines the sign without computing the actual product value.
Intuition
When we multiply numbers together, what really determines the sign of the final product? Let's think about the properties of multiplication:
- Any number multiplied by
0
gives0
- Positive × Positive = Positive
- Negative × Negative = Positive
- Positive × Negative = Negative
This means if there's even a single 0
in the array, the entire product becomes 0
regardless of other values.
For non-zero numbers, we notice that the actual magnitude doesn't matter - only whether each number is positive or negative. A negative number flips the sign of our running product, while a positive number keeps it the same.
Consider these examples:
[2, 3, -4]
: Start positive → stays positive after2
→ stays positive after3
→ flips to negative after-4
[-1, -2, 3]
: Start positive → flips to negative after-1
→ flips back to positive after-2
→ stays positive after3
We can track this sign-flipping behavior without calculating the actual product. Start with ans = 1
(positive), and for each negative number we encounter, multiply ans
by -1
to flip its sign. Positive numbers don't change the sign, so we can skip them.
This approach avoids overflow issues that could occur if we actually multiplied large numbers together. We only care about the sign, not the magnitude, so we can work with just 1
and -1
values throughout the traversal.
Learn more about Math patterns.
Solution Approach
The implementation uses a direct traversal approach with a sign-tracking variable.
We initialize an answer variable ans = 1
to represent a positive sign initially. This variable will hold either 1
(positive) or -1
(negative) throughout the traversal.
The algorithm works as follows:
-
Traverse each element
v
in the arraynums
-
Check for zero: If
v == 0
, immediately return0
since any product containing zero equals zero -
Handle negative numbers: If
v < 0
, multiplyans
by-1
to flip its sign- If
ans
was1
, it becomes-1
- If
ans
was-1
, it becomes1
- If
-
Skip positive numbers: Positive numbers don't affect the sign, so no action needed
-
Return the final sign: After traversing all elements,
ans
contains the sign of the product
Here's how the code executes for nums = [-1, -2, -3, 4, 5]
:
- Start:
ans = 1
- Process
-1
: negative, soans = 1 * (-1) = -1
- Process
-2
: negative, soans = -1 * (-1) = 1
- Process
-3
: negative, soans = 1 * (-1) = -1
- Process
4
: positive, skip - Process
5
: positive, skip - Return:
-1
The time complexity is O(n)
where n
is the length of the array, as we traverse it once. The space complexity is O(1)
since we only use a constant amount of extra space for the ans
variable.
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through the solution with nums = [2, -3, 0, -4]
.
Step 1: Initialize ans = 1
(representing positive sign)
Step 2: Process first element 2
2 > 0
, so it's positive- No action needed,
ans
remains1
Step 3: Process second element -3
-3 < 0
, so it's negative- Flip the sign:
ans = 1 * (-1) = -1
Step 4: Process third element 0
0 == 0
, so we found a zero- Immediately return
0
(the product will be zero)
The function returns 0
without needing to check the remaining element -4
.
Let's try another example without zeros: nums = [-2, 3, -5]
Step 1: Initialize ans = 1
Step 2: Process -2
-2 < 0
, it's negative- Flip sign:
ans = 1 * (-1) = -1
Step 3: Process 3
3 > 0
, it's positive- No action needed,
ans
remains-1
Step 4: Process -5
-5 < 0
, it's negative- Flip sign:
ans = -1 * (-1) = 1
Step 5: Return ans = 1
The product would be (-2) * 3 * (-5) = 30
which is positive, confirming our result of 1
.
Solution Implementation
1class Solution:
2 def arraySign(self, nums: List[int]) -> int:
3 """
4 Determine the sign of the product of all elements in the array.
5
6 Args:
7 nums: List of integers
8
9 Returns:
10 1 if product is positive, -1 if negative, 0 if product is zero
11 """
12 # Initialize sign as positive (1)
13 sign = 1
14
15 # Iterate through each number in the array
16 for num in nums:
17 # If any number is 0, the product will be 0
18 if num == 0:
19 return 0
20
21 # If number is negative, flip the sign
22 if num < 0:
23 sign *= -1
24
25 # Return the final sign of the product
26 return sign
27
1class Solution {
2 /**
3 * Determines the sign of the product of all elements in the array.
4 *
5 * @param nums The input array of integers
6 * @return 1 if product is positive, -1 if negative, 0 if product is zero
7 */
8 public int arraySign(int[] nums) {
9 // Initialize the sign as positive (1)
10 int sign = 1;
11
12 // Iterate through each number in the array
13 for (int number : nums) {
14 // If any number is zero, the product will be zero
15 if (number == 0) {
16 return 0;
17 }
18
19 // If the number is negative, flip the sign
20 if (number < 0) {
21 sign *= -1;
22 }
23 }
24
25 // Return the final sign of the product
26 return sign;
27 }
28}
29
1class Solution {
2public:
3 int arraySign(vector<int>& nums) {
4 // Initialize the sign as positive (1)
5 int sign = 1;
6
7 // Iterate through each number in the array
8 for (int num : nums) {
9 // If any number is 0, the product is 0
10 if (num == 0) {
11 return 0;
12 }
13
14 // If the number is negative, flip the sign
15 if (num < 0) {
16 sign *= -1;
17 }
18 }
19
20 // Return the final sign of the product
21 return sign;
22 }
23};
24
1/**
2 * Determines the sign of the product of all elements in an array
3 * @param nums - Array of integers
4 * @returns 1 if product is positive, -1 if negative, 0 if product is zero
5 */
6function arraySign(nums: number[]): number {
7 // Initialize result as positive (1)
8 let result: number = 1;
9
10 // Iterate through each number in the array
11 for (const num of nums) {
12 // If any element is 0, the product will be 0
13 if (num === 0) {
14 return 0;
15 }
16
17 // If element is negative, flip the sign of result
18 if (num < 0) {
19 result *= -1;
20 }
21 }
22
23 // Return the final sign of the product
24 return result;
25}
26
Time and Space Complexity
The time complexity is O(n)
, where n
is the length of the input array nums
. This is because the algorithm iterates through each element of the array exactly once in a single loop. Each operation inside the loop (checking if a value equals 0, checking if a value is negative, and multiplying by -1) takes constant time O(1)
.
The space complexity is O(1)
. The algorithm only uses a single variable ans
to track the sign of the product, regardless of the input size. No additional data structures are created that grow with the input size, making the space usage constant.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Attempting to Calculate the Actual Product
The most common mistake is trying to compute the actual product of all elements and then determining its sign:
# WRONG APPROACH - prone to overflow
def arraySign(self, nums: List[int]) -> int:
product = 1
for num in nums:
product *= num # This can overflow!
if product > 0:
return 1
elif product < 0:
return -1
else:
return 0
Why it fails: For large arrays with big numbers, the product quickly exceeds integer limits, causing overflow errors. For example, [100, 100, 100, 100, 100]
would result in 10,000,000,000
which may cause issues in some systems.
Solution: Only track the sign changes, never calculate the actual product value.
2. Forgetting to Handle Zero Early
Another pitfall is checking for zeros after processing all elements:
# INEFFICIENT APPROACH
def arraySign(self, nums: List[int]) -> int:
sign = 1
has_zero = False
for num in nums:
if num == 0:
has_zero = True # Still continues processing!
elif num < 0:
sign *= -1
return 0 if has_zero else sign
Why it's inefficient: Once we encounter a zero, we know the answer is 0. Continuing to process remaining elements wastes time.
Solution: Return immediately upon finding a zero with an early exit strategy.
3. Using Complex Counting Logic
Some solutions unnecessarily count negative numbers and then determine the sign based on odd/even count:
# OVERCOMPLICATED APPROACH
def arraySign(self, nums: List[int]) -> int:
negative_count = 0
for num in nums:
if num == 0:
return 0
if num < 0:
negative_count += 1
return -1 if negative_count % 2 == 1 else 1
Why it's overcomplicated: While this works, it adds unnecessary complexity with modulo operations and counting logic when simple sign flipping achieves the same result more intuitively.
Solution: Use direct sign multiplication (sign *= -1
) which is cleaner and more readable.
Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!