Coding interview problems › Arrays & Hashing

#️⃣ Arrays & Hashing Medium

Maximum Product Subarray

Maximum Product Subarray explained: track both the max and min product ending at each index, because a negative flips them. Tested Python and a live visual.

Also searched as: maximum product subarray with negatives · Kadane for product

📈

Try it live Free

Prefix Sums & Kadane

Watch Kadane keep a running value and drop it when it stops helping. For products, imagine carrying two running values, the biggest and the smallest, because a negative swaps them.

Open the playground →

The problem

Given a non-empty list of integers, find the largest product of any contiguous, non-empty subarray.

Inputnums = [2, 3, -2, 4]
Output6

[2, 3].

Inputnums = [-2, 3, -4]
Output24

Two negatives multiply to a positive.

The key insight

This is Kadane with a twist: multiplying by a negative number turns the smallest product into the largest. So track both the max and the min product of a subarray ending at the current index. When the next number is negative, they swap roles.

Brute force first: Computing the product of every subarray is O(n²).

Step-by-step approach

  1. Set hi = lo = best = nums[0].
  2. For each next x, compute the candidates x, hi * x and lo * x.
  3. New hi is the max of the three, new lo the min (compute both from the old values).
  4. Update best = max(best, hi) and return it at the end.
  5. A zero resets both naturally, because the candidate x itself wins.

Python solution

PYTHON 3tested
def max_product(nums):
    hi = lo = best = nums[0]
    for x in nums[1:]:
        cands = (x, hi * x, lo * x)
        hi, lo = max(cands), min(cands)    # use old hi and lo together
        best = max(best, hi)
    return best

Complexity

TimeO(n)
SpaceO(1)

One pass, keeping only the max and min product ending at the current index.

Common mistakes

Frequently asked questions

What is the time and space complexity of Maximum Product Subarray?

O(n) time and O(1) space, tracking the maximum and minimum product of a subarray ending at each index.

Why do we need the minimum product?

A very negative product becomes very positive after multiplying by another negative. Without the minimum you would lose that future best answer.

How are zeros handled?

At a zero all three candidates involve 0 or x = 0, so hi and lo both become 0, and the next element starts a fresh subarray through the x candidate.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Arrays & Hashing Hash Tables lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.