Is Maximum Product Subarray easy or hard?

Maximum Product Subarray is considered a medium difficulty problem. The challenge comes from handling negative numbers and zeros correctly, which requires tracking both maximum and minimum products instead of only a running maximum.

How to solve Maximum Product Subarray in O(n)?

Iterate through the array while keeping two values: the maximum product and minimum product ending at the current index. For each element, compute the new candidates using the current number, number × previous max, and number × previous min. Update the global maximum after each step. This single pass produces the result in O(n) time.

What is the best approach for Maximum Product Subarray?

The most efficient approach uses dynamic programming with two variables that track the maximum and minimum product ending at each index. This handles negative numbers because a negative value can turn a small minimum product into a large maximum. The algorithm runs in O(n) time and O(1) space.

What data structure is used in Maximum Product Subarray?

The problem primarily uses arrays and dynamic programming concepts. Instead of storing a full DP table, the optimized solution keeps only two variables representing the current maximum and minimum products, reducing memory usage to constant space.

What is the time complexity of Maximum Product Subarray?

The optimal solutions run in O(n) time because the array is scanned once while updating running products. Both the dynamic programming method and the prefix–suffix tracking approach maintain constant additional variables, giving O(1) space complexity.

Maximum Product Subarray Python or Java solution approach?

In Python or Java, maintain two variables for the current maximum and minimum product and iterate through the array once. At each step compute new candidates using multiplication with the current element, then update the result. This implementation runs in O(n) time and O(1) space.

Is Maximum Product Subarray asked at Google, Amazon, or Meta?

Maximum Product Subarray is a common medium-level interview problem that has appeared in coding interviews at companies like Amazon, Google, and Meta. It tests understanding of dynamic programming, handling negative numbers, and reasoning about subarray products.

Description Solution Video 15:31

152. Maximum Product Subarray

Medium37.3% acceptance23 companies

Given an integer array nums, find a subarray that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:

1 <= nums.length <= 2 * 10⁴
-10 <= nums[i] <= 10
The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

Asked at top 20 of 23 companies

Delhivery Juspay

TCS LinkedIn Adobe Morgan Stanley Hashedin Siemens Meta Qualcomm Swiggy

Google

+8 more

Amazon Microsoft Bloomberg

IBM Walmart Labs D. E. Shaw ServiceNow Tiktok

Topics

Array Dynamic Programming

15:31

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

152. Maximum Product Subarray

Asked at top 20 of 23 companies

Topics

Similar problems