1822. Sign of the Product of an Array

There is a function signFunc(x) that returns:
1 if x is positive.
-1 if x is negative.
0 if x is equal to 0.
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) = 1

Example 2:
Input: nums = [1,5,0,2,-3]
Output: 0
Explanation: The product of all values in the array is 0, and signFunc(0) = 0

Example 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

https://leetcode.com/problems/sign-of-the-product-of-an-array/


Video coming soon!



Subscribe for more updates


Algorithm/Insights

Approach 1: Calculate product and determine sign
The straightforward approach is to calculate the product of all the elements in the array and then determine the sign of the product. We can do this by iterating through the array and multiplying each element to a variable that we initialize to 1. After the loop, we can use a simple function to determine the sign of the product.

The main problem with this approach is that it involves calculating the product of all elements in the array, which can be computationally expensive and time-consuming for very large arrays. This can result in performance issues, especially if the product of the array exceeds the range of the data type being used to store it. In addition, calculating the product of the array may not be necessary to determine the sign of the product, as shown in the next approach. Therefore, this approach may not be the most efficient or optimal solution to the problem.

Approach 2: Determine sign without calculating product
An optimized approach is to determine the sign of the product without actually calculating the product. We can do this by counting the number of negative numbers in the array. If the number of negative numbers is even, then the product will be positive. If the number of negative numbers is odd, then the product will be negative. If the array contains a zero element, then the product will be zero.
The time complexity of both the approaches is O(n) where n is the length of the nums array since we need to iterate through all the elements in the array once.


Code Snippet

			
package com.ideserve.sakshi.questions;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * Sign of the Product of an Array
 *
 * @author Sakshi
 */
class Solution {
    public int arraySign(int[] nums) {
        int negative = 0;
        for (int num : nums) {
            if (num == 0) {
                return 0;
            }
            if (num < 0) {
                negative++;
            }
        }
        return ((negative & 1) == 0) ? 1 : -1;
    }
}
		

Order of the Algorithm

Time Complexity is O(n)
Space Complexity is O(1)


Contribution

  • Sincere thanks from IDeserve community to Sakshi Kataria for compiling current post.


    Sakshi Kataria