Log inSign up
mediumGeeksforGeeksNot Started

Minimum Product Subset

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Greedy
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an array a[] of N integers, find the minimum product possible with any non-empty subset of elements present in the array.

The subset can consist of a single element.

Modulo arithmetic is often applied for very large constraints, but here compute the exact minimum product (or modulo 10^9 + 7 where specified).

Example 1 · Example 1: Even Negatives:

Input: a = [-1, -1, -2, 4, 3]
Output: -24
Explanation: Negatives are [-1, -1, -2] (count = 3, odd). Take all negatives and all positives: (-1) * (-1) * (-2) * 4 * 3 = -24.

Example 2 · Example 2: All Positives with Zero:

Input: a = [0, 4, 5, 2]
Output: 0
Explanation: No negatives present, zero is present. Minimum product subset is [0], product = 0.

Constraints:

  • 1 <= N <= 105
  • -104 <= a[i] <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master greedy parity logic for multiplying negative numbers.
  • Handle edge cases cleanly (arrays with only zeros, only positives, single elements).
  • Implement the single-pass solution in C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Subset product optimization (minimum or maximum product).
  • Array contains mixture of negative, zero, and positive integers.
  • Non-empty subset constraint.

Algorithmic Decision Tree:

  • Track: countNeg, countZero, maxNeg (closest to 0), minPos.
  • Case 1: n == 1 -> return a[0].
  • Case 2: countNeg == 0 -> return (countZero > 0 ? 0 : minPos).
  • Case 3: countNeg is even -> product of all non-zeros except maxNeg.
  • Case 4: countNeg is odd -> product of all non-zeros.

Connected Patterns:

Maximum Product SubarrayMaximum Product of Three Numbers

1. Generate All Non-Empty Subsets

Intuition

Recursively generate all non-empty subsets of the array, calculate the product for each, and track the minimum.

Algorithm

  1. Step 1: Initialize minProd = infinity.
  2. Step 2: Define backtrack(idx, currentProd, hasElement).
  3. Step 3: At each index, branch into including a[idx] or excluding a[idx].
  4. Step 4: Update minProd when hasElement is true.
  5. Step 5: Return minProd.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8 long long minProd = 1e18;
9 void backtrack(int idx, long long currentProd, bool taken, const vector<int>& a) {
10 if (idx == a.size()) {
11 if (taken) minProd = min(minProd, currentProd);
12 return;
13 }
14 // Exclude
15 backtrack(idx + 1, currentProd, taken, a);
16 // Include
17 long long nextProd = taken ? currentProd * a[idx] : a[idx];
18 backtrack(idx + 1, nextProd, true, a);
19 }
20public:
21 long long minProductSubset(vector<int>& a) {
22 minProd = 1e18;
23 backtrack(0, 1, false, a);
24 return minProd;
25 }
26};
27
28int main() {
29 Solution sol;
30 vector<int> a = {-1, -1, -2, 4, 3};
31 cout << "Min Product: " << sol.minProductSubset(a) << endl;
32 return 0;
33}

Time & Space Complexity

  • Time complexity: O(2^N)
  • Space complexity: O(N)

2. Sorting Array Partitioning

Intuition

Sort the array. Collect negatives, zeros, and positives into separate lists, and greedily assemble the minimum product subset.

Algorithm

  1. Step 1: If n == 1, return a[0].
  2. Step 2: Sort the array ascending.
  3. Step 3: Count negatives and zeros.
  4. Step 4: If no negatives: if zero exists return 0, else return first element (min positive).
  5. Step 5: If even negatives: exclude the largest negative (the one closest to 0).
  6. Step 6: Multiply all remaining negatives and all positive elements.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 long long minProductSubset(vector<int>& a) {
10 int n = a.size();
11 if (n == 1) return a[0];
12
13 sort(a.begin(), a.end());
14
15 int countNeg = 0, countZero = 0;
16 for (int x : a) {
17 if (x < 0) countNeg++;
18 else if (x == 0) countZero++;
19 }
20
21 if (countNeg == 0) {
22 if (countZero > 0) return 0;
23 return a[0];
24 }
25
26 long long prod = 1;
27 int skipIdx = (countNeg % 2 == 0) ? countNeg - 1 : -1;
28
29 for (int i = 0; i < n; ++i) {
30 if (i == skipIdx || a[i] == 0) continue;
31 prod *= a[i];
32 }
33
34 return prod;
35 }
36};
37
38int main() {
39 Solution sol;
40 vector<int> a = {-1, -1, -2, 4, 3};
41 cout << "Min Product (Sorted): " << sol.minProductSubset(a) << endl;
42 return 0;
43}

Time & Space Complexity

  • Time complexity: O(N log N)
  • Space complexity: O(1) auxiliary

3. Single Pass Greedy Sign Analysis

Intuition

Iterate through the array in a single pass tracking negative count, zero count, maximum negative, minimum positive, and non-zero product.

Algorithm

  1. Step 1: If n == 1, return a[0].
  2. Step 2: Maintain countNeg = 0, countZero = 0, maxNeg = -infinity, minPos = infinity, prod = 1.
  3. Step 3: Scan each element: update counts, maxNeg, minPos, and multiply non-zeros into prod.
  4. Step 4: If countNeg == 0: if countZero > 0 return 0; else return minPos.
  5. Step 5: If countNeg is even: divide prod by maxNeg to remove the negative closest to zero.
  6. Step 6: Return prod.

Interactive Trace for Minimum Product Subset

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Step 1: Inspect a[0] = -1
Visual state
Values and pointers at this exact step
pointers
S
neg
pending
pending
pending
0
↑ i
1
2
3
Check / comparison
Negative number encountered.
Decision / next transition
countNeg = 1, maxNeg = -1.
Why this step matters

Step 1: Inspect a[0] = -1. Negative found. countNeg = 1, maxNeg = -1, prod = -1.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5using namespace std;
6
7class Solution {
8public:
9 long long minProductSubset(vector<int>& a) {
10 int n = a.size();
11 if (n == 1) return a[0];
12
13 int countNeg = 0, countZero = 0;
14 int maxNeg = -1e9;
15 int minPos = 1e9;
16 long long prod = 1;
17
18 for (int x : a) {
19 if (x == 0) {
20 countZero++;
21 continue;
22 }
23 if (x < 0) {
24 countNeg++;
25 maxNeg = max(maxNeg, x);
26 } else {
27 minPos = min(minPos, x);
28 }
29 prod *= x;
30 }
31
32 // If no negatives
33 if (countNeg == 0) {
34 if (countZero > 0) return 0;
35 return minPos;
36 }
37
38 // If even number of negatives, divide out the largest negative (closest to 0)
39 if (countNeg % 2 == 0) {
40 prod /= maxNeg;
41 }
42
43 return prod;
44 }
45};
46
47int main() {
48 Solution sol;
49 vector<int> a = {-1, -1, -2, 4, 3};
50 cout << "Min Product (Optimal): " << sol.minProductSubset(a) << endl;
51 return 0;
52}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(1)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — All Non-Empty SubsetsO(2^N)O(N)Generate all 2N - 1 non-empty subsets, compute product of each subset, and track the global minimum.Subset enumeration.
2.Better — Sorting by MagnitudeO(N log N)O(1) auxiliarySort the array. Explicitly isolate negatives, zeros, and positives, and assemble the minimum product subset.Sorting operation.
3.Optimal — Single Pass Greedy Sign AnalysisOptimalO(N)O(1)Scan array once: count negatives and zeros, find max negative and min positive, and multiply all non-zeros. Apply parity adjustment in O(1).Single linear pass.
Back to DSA Sheet