Problem Statement in English

You’re given an integer array nums. You need to find the contiguous subarray within an array (containing at least one number) which has the largest product.

Approach

Full disclosure: this is not my code, I got this online from NeetCode (brilliant channel by the way, definitely check him out).

We can solve this problem using the Kadane’s algorithm.

The way we do this is straightforward, but rather unusual, and so coming up with this unless you’ve seen it before is..probably not happening.

We keep track of the current minimum and maximum values. We then update the current minimum and maximum values by multiplying the current minimum and maximum values with the current number.

We also update the best value by taking the maximum of the current maximum and the best value.

Solution in Python


class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # global best
        best = nums[0]

        # local min
        currMin = 1

        # local max
        currMax = 1

        # iterate over the numbers
        for num in nums:

            # calculate the product of the current number 
            # with the current min
            v1 = currMin * num

            # calculate the product of the current number 
            # with the current max
            v2 = currMax * num

            # update the current min
            currMin = min(v1, v2, num)
            # update the current max
            currMax = max(v1, v2, num)

            # update the best value
            best = max(best, currMax)

        # return the best value
        return best

Complexity

  • Time: $O(n)$
    Since we iterate over $n$ elements at most.

  • Space: $O(1)$
    Since we store the current minimum and maximum values.

Mistakes I Made

I initially thought of multiplying all consecutive non-negative, non zero numbers together, since you have to multiply all such numbers in the subarray, as they’ll never reduce the product.

I then ran the $n^2$ search on it, and it actually got accepted. No TLE.

But I didn’t come up with the optimal solution on my own, and had to look it up.

And we are done.