Leetcode 1822. Sign of the Product of an Array Solution
Problem Description
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
Approach
To solve the problem, we need to find the product of all the integers in the array and then we can call the signFunc() function on the result. However, since we know that the product of two negative numbers is positive and the product of a positive and a negative number is negative, we can optimize the solution by iterating through the array and updating a variable to store the sign of the product as we go along.
If we encounter a 0, we can directly return 0 because the product would be 0 regardless of the other numbers. If we encounter a negative number, we can invert the sign without needing to compute the product at each step.
Example
Let's walk through an example: nums = [-1, -2, -3, -4, 3, 2, 1]
- Initialize the variable
signto 1. - Iterate through the array:
- nums[0] = -1, the number is negative, so update the sign by inverting it: sign = -1 * 1 = -1
- nums[1] = -2, the number is negative, so update the sign by inverting it: sign = -1 * -1 = 1
- nums[2] = -3, the number is negative, so update the sign by inverting it: sign = -1 * 1 = -1
- nums[3] = -4, the number is negative, so update the sign by inverting it: sign = -1 * -1 = 1
- nums[4] = 3, the number is positive, so no change to the sign
- nums[5] = 2, the number is positive, so no change to the sign
- nums[6] = 1, the number is positive, so no change to the sign
- Return the final sign value, which is 1.
Solution in Python
1class Solution:
2 def arraySign(self, nums):
3 sign = 1
4
5 for num in nums:
6 if num == 0:
7 return 0
8 if num < 0:
9 sign = -sign
10
11 return sign
Solution in Java
1class Solution {
2 public int arraySign(int[] nums) {
3 int sign = 1;
4
5 for (int num : nums) {
6 if (num == 0) {
7 return 0;
8 }
9 if (num < 0) {
10 sign = -sign;
11 }
12 }
13
14 return sign;
15 }
16}
Solution in JavaScript
1class Solution {
2 arraySign(nums) {
3 let sign = 1;
4
5 for (const num of nums) {
6 if (num === 0) {
7 return 0;
8 }
9 if (num < 0) {
10 sign = -sign;
11 }
12 }
13
14 return sign;
15 }
16}
Solution in C++
1class Solution {
2 public:
3 int arraySign(vector<int>& nums) {
4 int sign = 1;
5
6 for (const int num : nums) {
7 if (num == 0)
8 return 0;
9 if (num < 0)
10 sign = -sign;
11 }
12
13 return sign;
14 }
15};
Solution in C#
1public class Solution {
2 public int ArraySign(int[] nums) {
3 int sign = 1;
4
5 foreach (int num in nums) {
6 if (num == 0) {
7 return 0;
8 }
9 if (num < 0) {
10 sign = -sign;
11 }
12 }
13
14 return sign;
15 }
16}
17```## Summary
18
19In this article, we have showcased how to optimize a simple problem by avoiding unnecessary computations. The key idea is that, instead of calculating the product of all values in the array, we can just iterate through the array and update the sign of the product at each step based on the current number being processed.
20
21We have provided solutions in Python, JavaScript, Java, C++, and C#. In all cases, the code is similar and the time complexity is O(n), where n is the length of the input array.
22
23These optimized solutions are a good reminder of the importance of considering the characteristics of the problem at hand and not just blindly applying a formula or algorithm.