Maximum Product Subarray in DSA Python - Time & Space Complexity

Time Complexity: Maximum Product Subarray

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the maximum product of a subarray changes as the input size grows.

How does the number of steps grow when the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def max_product_subarray(nums):
    max_prod = min_prod = result = nums[0]
    for num in nums[1:]:
        candidates = (num, max_prod * num, min_prod * num)
        max_prod = max(candidates)
        min_prod = min(candidates)
        result = max(result, max_prod)
    return result

This code finds the maximum product of any contiguous subarray in the given list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: One loop that goes through the array once.
• How many times: Exactly once for each element after the first.

How Execution Grows With Input

Each new element adds a fixed number of steps to update max and min products and the result.

Input Size (n)	Approx. Operations
10	About 9 steps (one per element after first)
100	About 99 steps
1000	About 999 steps

Pattern observation: The number of steps grows directly with the size of the input.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the maximum product grows in a straight line as the input size grows.

Common Mistake

[X] Wrong: "Because we check multiple candidates each step, the time is O(n³)."

[OK] Correct: We only do a fixed number of checks per element, so the total steps grow linearly, not cubically.

Interview Connect

Understanding this linear time approach shows you can handle tricky problems efficiently, a skill valued in many coding challenges.

Self-Check

"What if we used nested loops to check all subarrays? How would the time complexity change?"