Find Minimum Product Subarray

Title: Find Minimum Product Subarray

In this guide, you’ll learn how to find the contiguous subarray within an integer array that has the minimum product, a close cousin of the well-known maximum product subarray problem. We’ll build a single-pass Java solution, trace it by hand on a concrete input, and work through the mistakes and edge cases that come up most often when this question shows up in interviews.

Understanding the Problem

Given an array of integers that can include positive numbers, negative numbers, and zeros, the goal is to find the contiguous subarray (containing at least one element) whose product of elements is the smallest possible. The subarray must be contiguous; you cannot skip elements or reorder them.

A brute-force approach would compute the product of every possible subarray and keep the smallest one, which takes O(n^2) time. The real challenge is recognizing that multiplying by a negative number can flip the largest running product into the smallest one, and vice versa, so a single running minimum is not enough.

Approach to Solve the Problem

1. Validate the input: throw IllegalArgumentException if nums is null or empty.
2. Initialize maxEndingHere, minEndingHere, and minProduct to nums[0], since any subarray’s product has to start somewhere.
3. Iterate from index 1 to the end of the array, treating each element as the end of a growing subarray.
4. Cache the previous maxEndingHere and minEndingHere in temporary variables before recomputing either one.
5. Recompute maxEndingHere and minEndingHere as the max and min of current, prevMax * current, and prevMin * current.
6. Update minProduct whenever the new minEndingHere is smaller than the running minProduct.
7. Return minProduct after the loop finishes.

Java Program

public class MinimumProductSubarray {

    public static int minProductSubarray(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("Array must not be null or empty");
        }

        int maxEndingHere = nums[0];
        int minEndingHere = nums[0];
        int minProduct = nums[0];

        for (int i = 1; i < nums.length; i++) {
            int current = nums[i];
            int prevMax = maxEndingHere;
            int prevMin = minEndingHere;

            maxEndingHere = Math.max(current, Math.max(prevMax * current, prevMin * current));
            minEndingHere = Math.min(current, Math.min(prevMax * current, prevMin * current));

            minProduct = Math.min(minProduct, minEndingHere);
        }

        return minProduct;
    }

    public static void main(String[] args) {
        int[] nums = {2, 3, -2, 4};
        System.out.println("Minimum product subarray: " + minProductSubarray(nums));
    }
}

Explanation of the Program

• maxEndingHere and minEndingHere track the largest and smallest product of any subarray that ends exactly at index i.
• Multiplying by a negative current can turn yesterday’s maximum into today’s minimum, so both prevMax and prevMin feed into the next maxEndingHere and minEndingHere.
• prevMax and prevMin are cached before either variable is reassigned, so the minEndingHere update never reads a value that was already overwritten this iteration.
• minProduct is updated on every iteration by comparing against minEndingHere, since the overall minimum can appear partway through the array rather than at the last index.
• The method throws IllegalArgumentException for a null or empty array instead of silently returning a sentinel value that could be mistaken for a real product.

Step-by-Step Trace

Consider nums = [2, -3, -2, 4, -1], where the final answer is -48, the product of the entire array. The table below shows minEndingHere and minProduct before and after processing each index from 1 onward; index 0 only seeds the initial values with 2.

At the end of each iteration, minProduct holds the minimum product of any subarray that ends at or before the current index. Notice iteration 2 does not change minProduct, because -2 is not smaller than the -6 already found.

Examples

Example 1: Array Containing Zero

int[] nums = {0, 2, -3, 4, -1};
System.out.println(minProductSubarray(nums)); // -24

The subarray [2, -3, 4] produces a product of -24, which beats every subarray that passes through the leading zero. Because multiplying by nums[i] = 0 resets maxEndingHere and minEndingHere back toward zero, the algorithm treats the zero as a natural boundary without any special-case code.

Example 2: All Negative Elements

int[] nums = {-1, -3, -2};
System.out.println(minProductSubarray(nums)); // -6

With three negative numbers, the product of the whole array is -6, while the product of just the last two elements, -3 and -2, is the positive number 6. The algorithm correctly rejects that pair because it tracks the running maximum separately and only reports the true minimum.

Example 3: Single Negative Element

int[] nums = {-7};
System.out.println(minProductSubarray(nums)); // -7

When the array has only one element, that element is both the smallest and largest possible product, so minProductSubarray returns it directly without ever entering the loop.

Common Mistakes to Avoid

These are the mistakes that most often turn this problem into a bug hunt rather than a clean pass.

• Initializing minEndingHere and minProduct to 0 – on an all-positive array like {1, 2, 3}, 0 is wrongly treated as smaller than every real product and the method returns 0 instead of 1. Initialize both to nums[0].
• Returning the last minEndingHere instead of a tracked minProduct – the smallest product can appear partway through the array, so using only the final iteration’s minEndingHere misses it. Update a separate minProduct on every iteration and return that.
• Tracking only a running minimum – multiplying minEndingHere by a negative nums[i] can produce a large positive value instead of the new minimum, since the true minimum can come from flipping the running maximum. Maintain maxEndingHere alongside minEndingHere at every index.
• Reusing maxEndingHere before computing minEndingHere – if maxEndingHere is reassigned first, the minEndingHere calculation reads an already-updated value instead of the previous iteration’s value, corrupting the result. Cache both previous values in temporary variables before reassigning either.
• Ignoring integer overflow on large inputs – multiplying several large-magnitude negative numbers can overflow int silently and flip the sign of what should be the minimum. Use long accumulators when the input range is large enough to risk overflow.

Edge Cases to Test

Walk through these input shapes before calling the problem solved.

• Empty array
• Single-element array
• Array containing one or more zeros
• All negative elements with an odd count
• All negative elements with an even count
• All positive elements
• Integer.MIN_VALUE or Integer.MAX_VALUE present
• Null array reference

Additional Considerations

The algorithm runs in O(n) time, visiting each element exactly once and doing a constant amount of work per index. It needs only O(1) extra space for maxEndingHere, minEndingHere, and minProduct, which is a significant improvement over the O(n^2) brute-force approach that checks every subarray’s product directly.

Because the recurrence depends only on the previous iteration’s maxEndingHere and minEndingHere, the same logic can run over a stream of numbers without storing the whole array, as long as you only need the minimum product and not the subarray’s boundaries.

If you also need to report which indices form the minimum-product subarray, track the start and end index alongside minProduct whenever it updates, rather than recomputing the subarray afterward.

Interview Follow-up Questions

An interviewer will usually push past the base solution with questions like these.

• What if the array contains only positive numbers? – no sign flips are possible, so maxEndingHere becomes unnecessary and the problem collapses to tracking a single running minimum product.
• What if the array can contain very large magnitude values that overflow a 32-bit product? – switch the accumulators to long, or compare using the sum of logarithms of absolute values plus a separate sign counter.
• What if the input arrives as a stream of unknown length? – keep maxEndingHere, minEndingHere, and minProduct as running state and update them as each value arrives; no array storage is needed.
• What if you need the K smallest subarray products instead of just one? – maintain a bounded max-heap of size K as you generate each minEndingHere, evicting the largest entry whenever the heap grows past size K.

Conclusion

Finding the minimum product subarray is a short extension of the classic maximum product subarray pattern once you recognize that negative numbers can swap the roles of the running maximum and minimum. Tracking both values in a single pass keeps the solution at O(n) time and O(1) space.

Try adapting the same two-variable tracking technique to problems like maximum product subarray or minimum sum subarray to see how often this pattern reappears in array problems. You can learn more about array-based interview problems in the Arrays category on this site.