Master Maximum Product Subarray (LeetCode 152): Modified Kadane’s | Day 8 of 180

# 180-Day DSA Roadmap | Day 8: Maximum Product Subarray (LeetCode #152)

* **Topic:** Arrays & Strings  
* **Pattern:** Kadane’s Algorithm Variation (Tracking Min & Max Simultaneously)  
* **Difficulty:** Medium  
* **LeetCode Problem:** LeetCode #152 - Maximum Product Subarray  
* **Target Companies:** Amazon, Google, Microsoft, Meta, LinkedIn, Apple  

---

## 1. Problem Statement

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.

A **subarray** is a contiguous, non-empty sequence of elements within an array.

### Constraints
* 1 <= nums.length <= 2 * 10^4
* -10 <= nums[i] <= 10
* The product of any prefix or suffix of `nums` is guaranteed to fit in a 32-bit integer.

### Example Walkthrough
```text
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 contiguous subarray.

2. Pattern Recognition: Why Classic Kadane’s Fails

On Day 7, we used Kadane’s Algorithm for Maximum Subarray Sum. Whenever the running sum dropped below zero, we discarded it because a negative sum always reduces the next number.

Multiplication changes the game entirely:

1. The Double Negative Flip: A very small negative number multiplied by another negative number turns into a very large positive number: (-10) * (-5) = +50
2. The Zero Reset: Any product multiplied by zero collapses to zero, forcing you to treat the next index as a potential fresh start.

Because of this, the minimum product ending at the previous index can become the maximum product at the current index if nums[i] is negative.

To adapt Kadane’s algorithm to products, you must track two running values at each step:

• max_so_far: The maximum product ending at index i.
• min_so_far: The minimum (most negative) product ending at index i.

3. Algorithmic Approaches

Approach 1: Brute Force (Suboptimal)

• Compute the product of every contiguous subarray (i, j) using nested loops.
• Time Complexity: O(N^2)
• Space Complexity: O(1)
• Verdict: Fails with Time Limit Exceeded (TLE) when N = 2 * 10^4.

Approach 2: Prefix and Suffix Scan (Clever Alternative)

• Scan from left to right computing prefix products, and right to left computing suffix products. Reset the running product to 1 whenever a zero is hit.
• Time Complexity: O(N)
• Space Complexity: O(1)
• Verdict: Clean and valid, but doesn’t build the dynamic programming intuition interviewers look for.

Approach 3: Modified Kadane’s with Min/Max Tracking (MNC Standard)

1. Initialize max_so_far = nums[0], min_so_far = nums[0], and result = nums[0].
2. Iterate through nums starting at index 1:
   • The Swap Trick: If nums[i] is negative, multiplying flips signs! A maximum becomes a minimum, and a minimum becomes a maximum.
     Therefore, swap max_so_far and min_so_far before calculating.
   • Update max_so_far = max(nums[i], max_so_far * nums[i]).
   • Update min_so_far = min(nums[i], min_so_far * nums[i]).
   • Update result = max(result, max_so_far).

Visual Execution Trace:
nums = [2, 3, -2, 4, -1]

Index	num	Action	max_so_far	min_so_far	result
Init	2	–	2	2	2
1	3	positive (no swap)	max(3, 6) = 6	min(3, 6) = 3	6
2	-2	negative –> SWAP max/min
		(max becomes 3, min is 6)
		compute:	max(-2, -6) = -2	min(-2, -12) = -12	6
3	4	positive (no swap)	max(4, -8) = 4	min(4, -48) = -48	6
4	-1	negative –> SWAP max/min
		(max becomes -48, min is 4)
		compute:	max(-1, 48) = 48	min(-1, -4) = -4	48 <– MAX!

Final Result: 48 (from subarray [-2, 4, -1] which equals 48)

4. Production-Ready Code Implementations

Java Solution

Java

class Solution {
    public int maxProduct(int[] nums) {
        int maxSoFar = nums[0];
        int minSoFar = nums[0];
        int result = nums[0];

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

            // If current number is negative, max and min swap roles
            if (current < 0) {
                int temp = maxSoFar;
                maxSoFar = minSoFar;
                minSoFar = temp;
            }

            maxSoFar = Math.max(current, maxSoFar * current);
            minSoFar = Math.min(current, minSoFar * current);

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

        return result;
    }
}

Python 3 Solution

Python

class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        max_so_far = nums[0]
        min_so_far = nums[0]
        result = nums[0]

        for i in range(1, len(nums)):
            curr = nums[i]

            # If current number is negative, max and min swap roles
            if curr < 0:
                max_so_far, min_so_far = min_so_far, max_so_far

            max_so_far = max(curr, max_so_far * curr)
            min_so_far = min(curr, min_so_far * curr)

            result = max(result, max_so_far)

        return result

C++ Solution

C++

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxProduct(std::vector<int>& nums) {
        int maxSoFar = nums[0];
        int minSoFar = nums[0];
        int result = nums[0];

        for (size_t i = 1; i < nums.size(); ++i) {
            int current = nums[i];

            // If current number is negative, max and min swap roles
            if (current < 0) {
                std::swap(maxSoFar, minSoFar);
            }

            maxSoFar = std::max(current, maxSoFar * current);
            minSoFar = std::min(current, minSoFar * current);

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

        return result;
    }
};

5. Complexity Analysis

• Time Complexity: O(N) — Single pass through the array. At each iteration, only constant-time comparisons and swaps occur.
• Space Complexity: O(1) — Only three scalar tracking variables (maxSoFar, minSoFar, result) are maintained.

6. Key Takeaways & Common Interview Traps

• The Stale Variable Bug: If you calculate minSoFar after updating maxSoFar without saving the old maxSoFar in a temp variable, you use the corrupted new value. Swapping before the math avoids this bug completely.
• Handling Zeros: When current == 0, both maxSoFar and minSoFar collapse to 0. In the next iteration, Math.max(nums[i], 0 * nums[i]) cleanly resets to nums[i], handling resets seamlessly.

<FollowUp label="Want Day 9: Subarray Sum Equals K (Pattern 5: Prefix Sum) in this exact copy block?" query="Generate Day 9: Subarray Sum Equals K (LeetCode #560) under Pattern 5 (Prefix Sum Technique) in the same single copy-paste block."/>

Master Maximum Product Subarray (LeetCode 152): Modified Kadane’s | Day 8 of 180


Master LeetCode 152 (Maximum Product Subarray) using modified Kadane’s algorithm. Handle negative numbers and zero with complete code in Java, Python, and C++.


Maximum Product Subarray LeetCode 152, Modified Kadanes Algorithm, Max Product Subarray Java Python Cpp, LeetCode 152 Solution


leetcode 152, maximum product subarray, kadanes algorithm, dynamic programming, array algorithms, contiguous subarray, dsa roadmap, dsa interview questions, coding interview preparation, data structures and algorithms, leetcode solutions, kadane pattern, leetcode medium, faang interview preparation, mnc coding questions, amazon coding interview, google coding interview, microsoft interview questions, meta coding interview, adobe coding questions, apple interview questions, leetcode 152 java, leetcode 152 python, leetcode 152 cpp, java dsa, python dsa, cpp dsa, time complexity o n, space complexity o 1, array interview questions, maximum product, negative number swap, top dsa patterns, software engineer jobs, campus placement preparation, competitive programming, vs coding academy, 180 days dsa, dsa cheat sheet, cracking the coding interview, tech interview prep, leetcode patterns, software development engineer, sde 1 preparation, single pass algorithm, coding questions for freshers, dsa placement series, engineering placements, leetcode practice, data structures roadmap

Siemens Recruitment 2026: Finance Trainee (B.Com / BBA Freshers) | Bangalore