Minimum Product Subset of an Array

Minimum Product of a Subset is a clean little greedy problem. You may pick any subset of the array, and you want the product of the picked elements to be as small as possible. The trick is realizing you almost always want to take everything — the only question is how the signs line up.

The slow way first

The brute-force idea: enumerate every subset, compute each product, and keep the minimum. There are 2^n subsets, so this is O(2ⁿ) — hopeless past a dozen elements.

But look closer. Each element only ever multiplies the product. A positive factor > 1 makes a positive product bigger and a negative product smaller — both move us away from zero, which is what we want. So we essentially never want to leave out a useful element. The whole problem collapses to a sign argument.

The idea: take everything, then fix the sign

Multiply all the non-zero elements together. Now reason about the result:

• Each negative factor flips the sign. With an odd number of negatives the product is already negative — the best possible direction.
• With an even number of negatives the product comes out positive, which is bad. To flip it negative we drop exactly one negative — the largest one (closest to zero, like -1) — because removing it changes the product the least while flipping the sign.

Zeros are special: a zero would force the product to 0. We skip them, unless the array is all non-positive in a way that makes 0 the best we can do.

The key insight: we want the most negative product, so an odd negative count is already a win, and an even count costs us one division by the closest-to-zero negative.

Walk through it

Step through the animation. The pointer x scans the array. Negatives are counted and max_neg tracks the one closest to zero. With [-1, -1, -2, 4, 3] the running product reaches -24 and the negative count is 3 — odd — so we keep the full product as the answer.

Pseudocode

product = 1
negatives = 0
max_neg = -infinity          # largest (closest to zero) negative
for each x in nums:
    if x == 0: skip it
    if x < 0:
        negatives += 1
        max_neg = max(max_neg, x)
    product *= x
if negatives is even and negatives > 0:
    product = product / max_neg   # drop one negative to flip the sign
return product

The Python solution

def min_product_subset(nums):
    product = 1
    negatives = 0
    max_neg = float("-inf")
    zeros = 0
    for x in nums:
        if x == 0:
            zeros += 1
            continue
        if x < 0:
            negatives += 1
            max_neg = max(max_neg, x)
        product *= x
    if negatives % 2 == 0 and negatives > 0:
        product //= max_neg
    return product

• We multiply only non-zero elements into product, skipping any zero with continue.
• negatives counts the negative factors and max_neg keeps the one closest to zero (a max over negatives).
• After the loop, an odd negative count means product is already negative — we return it as is.
• Line 14 catches the even case (positive product); line 15 divides out max_neg, removing one negative so the sign flips while losing the least magnitude.
• The negatives > 0 guard avoids dividing when there were no negatives at all.

Complexity

We replace exponential subset enumeration with a single linear scan and a constant amount of bookkeeping — a huge win, and the space is O(1).

When this pattern shows up

Practice