algoadvance

Leetcode 1822. Sign of the Product of an Array

Problem Statement

You are provided with an integer array nums. You need to determine the sign of the product of all values in the array nums.

• If the product is positive, return 1.
• If the product is negative, return -1.
• If the product is zero, return 0.

Example:

1. Input: nums = [-1,-2,-3,-4,3,2,1]
   • Output: 1
2. Input: nums = [1,5,0,2,-3]
   • Output: 0
3. Input: nums = [-1,1,-1,1,-1]
   • Output: -1

Clarifying Questions

1. Q: Can the array contain only one element? A: Yes, the array can contain only one element.

2. Q: Can the input array contain positive, negative, and zero elements? A: Yes, the input can contain any combination of positive, negative, and zero elements.

3. Q: What is the expected size of the input array? A: The array length can vary, but for the sake of this problem, assume it is within the constraints typically imposed by LeetCode (e.g., up to 1000 elements).

Strategy

1. Iterate through the array elements:
   • If any element is 0, return 0 immediately because the product will be 0.
   • Count the number of negative numbers in the array.
2. If the count of negative numbers is odd, the sign of the product will be -1. If it’s even, the sign will be 1.

Time Complexity

• The algorithm requires iterating through the entire array once, making the time complexity O(n), where n is the number of elements in the array.

Code

public class Solution {
    public int arraySign(int[] nums) {
        int negativeCount = 0;
        
        for (int num : nums) {
            if (num == 0) {
                return 0;
            }
            if (num < 0) {
                negativeCount++;
            }
        }
        
        // If the count of negative numbers is odd, the product is negative
        if (negativeCount % 2 == 1) {
            return -1;
        } else {
            return 1;
        }
    }
}

Explanation of the Code

1. Initialization: We initialize a counter negativeCount to keep track of the number of negative elements.

2. Iteration:
   • For each element num in the array nums, we check if it is 0. If it is, we return 0 because the product will be 0.
   • If num is negative, we increment the negativeCount.
3. Return Result:
   • We check if negativeCount is odd or even.
   • If odd, return -1, indicating the product is negative.
   • Else, return 1, indicating the product is positive.

This approach ensures that we efficiently determine the sign of the product without actually computing the potentially large product.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?