Highest Product of Subarray

You sit down for an Adobe screen and hear: "Given an integer array, find the contiguous subarray with the highest product." If you have solved maximum subarray sum before, your instinct might be to apply Kadane's algorithm directly. But products behave differently than sums. A single negative number can turn a huge positive product into a huge negative one, and a second negative can flip it right back. This twist is exactly what makes Highest Product of Subarray (also known as Maximum Product Subarray) a favorite at companies like Apple, Google, Uber, and Amazon.

TL;DR

Track both a running maximum product and a running minimum product as you scan through the array. When you encounter a negative number, swap the two before multiplying. At each position, decide whether to extend the current subarray or start fresh from the current element. This runs in O(n) time and O(1) space. The key insight is that the most negative running product can become the most positive after hitting another negative, so you can never afford to discard it.

Why This Problem Matters

Maximum Product Subarray appears on the Blind 75 list and shows up frequently at Wayfair, Apple, Adobe, and Google. It is often asked as a follow-up to Maximum Subarray Sum, and interviewers use it to test whether you can adapt a known pattern (Kadane's algorithm) to handle a new constraint (sign changes under multiplication). If you can solve both problems cleanly, it signals strong command of single-pass array algorithms.

Understanding the Problem

Given an integer array nums, find a contiguous subarray that yields the highest product and return that product.

For the array [2, 3, -2, 4], the subarray [2, 3] gives the highest product of 6.

Constraints:

• 1 ≤ nums.length ≤ 2 * 10^4
• -10 ≤ nums[i] ≤ 10
• The product of any subarray fits in a 32-bit integer

Why Products Are Harder Than Sums

With Maximum Subarray Sum, you only track one running value. At each element, you either extend the current sum or start fresh. Whichever is larger wins.

With products, negative numbers create a problem. Suppose your running maximum product is 6 and you hit -2. The product becomes -12. But if you then hit another -3, that -12 * -3 = 36 is a new best. A sum algorithm would have thrown away the -12 and started over. A product algorithm cannot afford to, because the minimum (most negative) product might become the maximum later.

This is the fundamental difference: you need to track both the maximum and minimum running products at every position.

Edge Cases to Consider

1. Array contains zero: Zero kills any running product. Both max and min reset.
2. All negative numbers: The algorithm picks the best among single elements and pairs of negatives.
3. Single element: Return that element directly.
4. Two consecutive negatives: Their product is positive, potentially the answer.

Solution Approach

The algorithm scans left to right, maintaining three values:

• maxProduct: the largest product of any subarray ending at the current index
• minProduct: the smallest (most negative) product of any subarray ending at the current index
• result: the global maximum seen so far

At each element, you make three decisions:

1. If the current number is negative, swap maxProduct and minProduct. A negative times the old minimum gives a candidate for the new maximum, and a negative times the old maximum gives a candidate for the new minimum.

2. Update maxProduct to be the larger of the current number alone or maxProduct times the current number. This is the "extend or restart" decision.

3. Update minProduct similarly, choosing the smaller of the two.

4. Update result if maxProduct beats it.

Why the Swap Works

Consider the state just before processing a negative number:

Before the swap, max=6 and min=3 (from the subarray [2, 3]). When we hit -2, multiplying 6 by -2 gives -12 and multiplying 3 by -2 gives -6. The old max becomes the new min, and the old min becomes the new max. By swapping first, the standard max(num, maxProduct * num) and min(num, minProduct * num) operations produce the correct results without extra conditional logic.

Full Walkthrough: [2, 3, -2, 4]

Step by step:

• i=0 (num=2): Initialize all three variables to 2.
• i=1 (num=3): Positive, no swap. maxProduct = max(3, 23) = 6. minProduct = min(3, 23) = 3. result updates to 6.
• i=2 (num=-2): Negative, so swap max and min. After swap: max=3, min=6. Then maxProduct = max(-2, 3*-2) = max(-2, -6) = -2. minProduct = min(-2, 6*-2) = min(-2, -12) = -12. result stays at 6.
• i=3 (num=4): Positive, no swap. maxProduct = max(4, -24) = max(4, -8) = 4. minProduct = min(4, -124) = min(4, -48) = -48. result stays at 6.

Final answer: 6, from the subarray [2, 3].

When Negatives Produce the Answer: [-2, 3, -4]

At index 2, the minimum product of -6 (from [-2, 3]) gets multiplied by -4 to produce 24. Without tracking the minimum, we would have missed this entirely. The subarray [-2, 3, -4] gives 24.

Zero Resets Everything: [-2, 0, -1]

At index 1, multiplying anything by 0 gives 0. Both maxProduct and minProduct become 0, effectively restarting the search. The result is 0.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {

  public int maxProduct(int[] nums) {
    if (nums == null || nums.length == 0) {
      return 0;
    }

    int maxProduct = nums[0];
    int minProduct = nums[0];
    int result = nums[0];

    for (int i = 1; i < nums.length; i++) {
      // Negative number flips max and min
      if (nums[i] < 0) {
        int temp = maxProduct;
        maxProduct = minProduct;
        minProduct = temp;
      }

      // Extend the subarray or start fresh
      maxProduct = Math.max(nums[i], maxProduct * nums[i]);
      minProduct = Math.min(nums[i], minProduct * nums[i]);

      // Track global best
      result = Math.max(result, maxProduct);
    }

    return result;
  }
}

The algorithm initializes maxProduct, minProduct, and result to the first element. Then for each subsequent element, it checks if the number is negative (triggering a swap), updates the running products with extend-or-restart logic, and keeps track of the global maximum.

More Examples

All positives: [1, 2, 3, 4]

No swaps needed. The running product grows at every step, and the entire array is the answer: 24.

Mixed negatives: [2, -5, -2, -4, 3]

Three swaps happen at indices 1, 2, and 3. At index 2, the minimum product -10 gets multiplied by -2 to produce 20. At index 4, the max of 8 gets multiplied by 3 to produce 24. The answer is 24, from the subarray [-5, -2, -4, 3].

Complexity Analysis

Time Complexity: O(n)

The algorithm visits each element exactly once. At each position, it performs a constant number of operations: one comparison, a possible swap, two max/min calls, and one result update. No element is visited more than once.

Space Complexity: O(1)

Only three integer variables are maintained (maxProduct, minProduct, result) plus the loop counter. No arrays, hash maps, or recursion stacks are used.

Comparison with Brute Force

A brute force approach would compute the product of every subarray using two nested loops, running in O(n^2) time. For an array of 20,000 elements, that's 200 million operations. The single-pass approach does it in 20,000.

Common Pitfalls

1. Forgetting the minimum product: The most common mistake. If you only track maxProduct, inputs like [-2, 3, -4] return 3 instead of the correct 24.

2. Not swapping on negative: Some implementations try to handle negatives with extra if branches instead of a clean swap. This leads to subtle bugs when the current element is negative and both maxProduct and minProduct are also negative.

3. Confusing this with Kadane's: Directly applying Kadane's algorithm (tracking only a running max) fails because multiplication does not preserve sign the way addition does.

4. Forgetting zero handling: Zero multiplied by anything is zero. The algorithm handles this correctly through the max(nums[i], maxProduct * nums[i]) logic, which restarts the subarray when continuing would produce a worse result. But in testing, it is worth verifying inputs like [-2, 0, -1].

Interview Tips

When solving this problem in an interview:

1. Start by contrasting with max subarray sum: "This is like Kadane's, but multiplication means negative numbers can flip the sign. I need to track both a running max and a running min."

2. Explain the swap before coding: Walk through a small example like [-2, 3, -4] on the whiteboard. Show how the minimum product of -6 becomes the maximum of 24 at the last element.

3. Handle edge cases explicitly: Mention zero, all negatives, and single-element arrays. An interviewer at Google or Apple will expect you to identify these.

4. Know the follow-ups: "What if we wanted to return the actual subarray, not just the product?" Track start/end indices alongside the product variables.

Key Takeaways

• Track both maxProduct and minProduct at every position. The minimum can become the maximum after hitting a negative number, which is the core difference from Kadane's sum algorithm.
• Swap maxProduct and minProduct before multiplying when the current element is negative. This keeps the extend-or-restart logic clean and avoids branching errors.
• The max(nums[i], maxProduct * nums[i]) pattern is the extend-or-restart decision: either continue the current subarray or start a new one at this element.
• Zero acts as a natural subarray boundary by resetting both running products. The algorithm handles this without special-case code.
• Time O(n), space O(1). Every element is processed once, and only three variables are maintained regardless of input size.

Related Problems

Once you are comfortable with this problem, try these related challenges to deepen your understanding:

• Maximum Subarray Sum (Kadane's algorithm, the simpler additive version)
• Maximum Product of Three Numbers
• Product of Array Except Self
• Maximum Length of Subarray with Positive Product

This problem and thousands of others are available on Firecode, where over 50,000 users have prepared for technical interviews and landed roles at top tech companies. The spaced-repetition engine will schedule this problem for review at the right intervals so the max/min tracking pattern stays fresh when interview day comes.

Solutions in Other Languages

Python

class Solution:
    def max_product(self, nums):
        if not nums:
            return 0

        max_product = min_product = result = nums[0]

        for num in nums[1:]:
            if num < 0:
                max_product, min_product = min_product, max_product

            max_product = max(num, max_product * num)
            min_product = min(num, min_product * num)

            result = max(result, max_product)

        return result

JavaScript

class Solution {
  maxProduct(nums) {
    if (nums.length === 0) return 0;

    let maxProduct = nums[0];
    let minProduct = nums[0];
    let result = nums[0];

    for (let i = 1; i < nums.length; i++) {
      if (nums[i] < 0) {
        [maxProduct, minProduct] = [minProduct, maxProduct];
      }

      maxProduct = Math.max(nums[i], maxProduct * nums[i]);
      minProduct = Math.min(nums[i], minProduct * nums[i]);

      result = Math.max(result, maxProduct);
    }

    return result;
  }
}

TypeScript

class Solution {
  maxProduct(nums: number[]): number {
    if (nums.length === 0) return 0;

    let maxProduct = nums[0];
    let minProduct = nums[0];
    let result = nums[0];

    for (let i = 1; i < nums.length; i++) {
      if (nums[i] < 0) {
        [maxProduct, minProduct] = [minProduct, maxProduct];
      }

      maxProduct = Math.max(nums[i], maxProduct * nums[i]);
      minProduct = Math.min(nums[i], minProduct * nums[i]);

      result = Math.max(result, maxProduct);
    }

    return result;
  }
}

C++

#include <vector>
#include <algorithm>

class Solution {
public:
  int maxProduct(std::vector<int> &nums) {
    if (nums.empty()) return 0;

    int maxProduct = nums[0];
    int minProduct = nums[0];
    int result = nums[0];

    for (size_t i = 1; i < nums.size(); ++i) {
      if (nums[i] < 0) {
        std::swap(maxProduct, minProduct);
      }

      maxProduct = std::max(nums[i], maxProduct * nums[i]);
      minProduct = std::min(nums[i], minProduct * nums[i]);

      result = std::max(result, maxProduct);
    }

    return result;
  }
};

Go

func MaxProduct(nums []int) int {
    if len(nums) == 0 {
        return 0
    }

    maxProduct := nums[0]
    minProduct := nums[0]
    result := nums[0]

    for i := 1; i < len(nums); i++ {
        if nums[i] < 0 {
            maxProduct, minProduct = minProduct, maxProduct
        }

        maxProduct = max(nums[i], maxProduct*nums[i])
        minProduct = min(nums[i], minProduct*nums[i])

        result = max(result, maxProduct)
    }

    return result
}

Scala

class Solution {
  def maxProduct(nums: Array[Int]): Int = {
    if (nums.isEmpty) return 0

    var maxProduct = nums(0)
    var minProduct = nums(0)
    var result = nums(0)

    for (i <- 1 until nums.length) {
      val num = nums(i)
      if (num < 0) {
        val temp = maxProduct
        maxProduct = minProduct
        minProduct = temp
      }

      maxProduct = Math.max(num, maxProduct * num)
      minProduct = Math.min(num, minProduct * num)

      result = Math.max(result, maxProduct)
    }

    result
  }
}

Swift

class Solution {
    func maxProduct(_ nums: [Int]) -> Int {
        if nums.isEmpty {
            return 0
        }

        var maxProduct = nums[0]
        var minProduct = nums[0]
        var result = nums[0]

        for i in 1..<nums.count {
            if nums[i] < 0 {
                let temp = maxProduct
                maxProduct = minProduct
                minProduct = temp
            }

            maxProduct = max(nums[i], maxProduct * nums[i])
            minProduct = min(nums[i], minProduct * nums[i])

            result = max(result, maxProduct)
        }

        return result
    }
}

Kotlin

class Solution {
  fun maxProduct(nums: IntArray): Int {
    if (nums.isEmpty()) {
      return 0
    }

    var maxProduct = nums[0]
    var minProduct = nums[0]
    var result = nums[0]

    for (i in 1 until nums.size) {
      if (nums[i] < 0) {
        val temp = maxProduct
        maxProduct = minProduct
        minProduct = temp
      }

      maxProduct = maxOf(nums[i], maxProduct * nums[i])
      minProduct = minOf(nums[i], minProduct * nums[i])

      result = maxOf(result, maxProduct)
    }

    return result
  }
}

Ruby

class Solution
  def max_product(nums)
    return 0 if nums.nil? || nums.empty?

    max_product = min_product = result = nums[0]

    nums[1..].each do |num|
      max_product, min_product = min_product, max_product if num < 0

      max_product = [num, max_product * num].max
      min_product = [num, min_product * num].min

      result = [result, max_product].max
    end

    result
  end
end

Rust

pub fn max_product(nums: Vec<i32>) -> i32 {
    if nums.is_empty() {
        return 0;
    }

    let mut max_product = nums[0];
    let mut min_product = nums[0];
    let mut result = nums[0];

    for i in 1..nums.len() {
        if nums[i] < 0 {
            std::mem::swap(&mut max_product, &mut min_product);
        }

        max_product = std::cmp::max(nums[i], max_product * nums[i]);
        min_product = std::cmp::min(nums[i], min_product * nums[i]);

        result = std::cmp::max(result, max_product);
    }

    result
}

C#

public class Solution {
    public int maxProduct(int[] nums) {
        if (nums == null || nums.Length == 0) {
            return 0;
        }

        int maxProduct = nums[0];
        int minProduct = nums[0];
        int result = nums[0];

        for (int i = 1; i < nums.Length; i++) {
            if (nums[i] < 0) {
                int temp = maxProduct;
                maxProduct = minProduct;
                minProduct = temp;
            }

            maxProduct = Math.Max(nums[i], maxProduct * nums[i]);
            minProduct = Math.Min(nums[i], minProduct * nums[i]);

            result = Math.Max(result, maxProduct);
        }

        return result;
    }
}

Dart

import 'dart:math';

class Solution {
  int maxProduct(List<int> nums) {
    if (nums.isEmpty) {
      return 0;
    }

    int maxProd = nums[0];
    int minProd = nums[0];
    int result = nums[0];

    for (int i = 1; i < nums.length; i++) {
      if (nums[i] < 0) {
        int temp = maxProd;
        maxProd = minProd;
        minProd = temp;
      }

      maxProd = max(nums[i], maxProd * nums[i]);
      minProd = min(nums[i], minProd * nums[i]);

      result = max(result, maxProd);
    }

    return result;
  }
}

PHP

class Solution {
    public function maxProduct(array $nums): int {
        if (empty($nums)) {
            return 0;
        }

        $maxProduct = $nums[0];
        $minProduct = $nums[0];
        $result = $nums[0];

        for ($i = 1; $i < count($nums); $i++) {
            if ($nums[$i] < 0) {
                $temp = $maxProduct;
                $maxProduct = $minProduct;
                $minProduct = $temp;
            }

            $maxProduct = max($nums[$i], $maxProduct * $nums[$i]);
            $minProduct = min($nums[$i], $minProduct * $nums[$i]);

            $result = max($result, $maxProduct);
        }

        return $result;
    }
}