Min Product Subset

Problem Overview

A negative product is always smaller than a positive one, so use as many negatives as needed to make the sign negative while multiplying large magnitudes.

Intuition

A negative product is always smaller than a positive one, so use as many negatives as needed to make the sign negative while multiplying large magnitudes. That means: take the product of all non-zero elements when the negative count is odd; when it is even, drop the negative closest to zero (divide it out) so the sign flips. With no negatives, the minimum element wins (0 if a zero exists).

Algorithm

1Scan once: multiply all non-zeros into completeProduct, count negatives, track maxNeg (least-magnitude negative) and the overall min.
2If neg is odd, return completeProduct.
3If neg is 0, return min.
4Otherwise return completeProduct / maxNeg.

Example Walkthrough

Input: arr = [4, -2, 5]

1. One negative, non-zero product = 4*(-2)*5 = -40.
2. Odd negatives -> answer is -40.

Output: -40

Common Pitfalls

• Never multiply zeros into the running product - they only matter when no negative product is possible.
• For even negatives, remove maxNeg (closest to zero), not the most negative value.
• All-positive arrays: answer is the smallest element, not the full product.
• Single-element arrays are already the answer.

Min Product Subset.java

Java

// Approach: Min non-empty subset product. Multiply all non-zeros and count
// negatives; track the negative closest to zero (maxNeg) and the overall min.
// Odd negatives: product of non-zeros is already minimal. Even negatives:
// divide out maxNeg to flip the sign. No negatives: answer is the minimum
// element (0 if a zero exists, else the smallest positive).
// Complexity: O(n) time and O(1) space.

class Solution {

    public int minProd(int[] arr) {
        int neg = 0;
        int maxNeg = Integer.MIN_VALUE;
        int completeProduct = 1;
        int min = Integer.MAX_VALUE;

        for (int x : arr) {
            if (x < 0) {
                neg++;
                maxNeg = Math.max(maxNeg, x);
            }
            if (x != 0) {
                completeProduct *= x;
            }
            min = Math.min(min, x);
        }

        if (neg % 2 != 0) {
            return completeProduct;
        }
        if (neg == 0) {
            return min;
        }
        return completeProduct / maxNeg;
    }
}

Was this solution helpful?