Maximum Product Subarray in DSA C - 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 subarray changes as the input array 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.

int maxProduct(int* nums, int numsSize) {
    int maxProd = nums[0], minProd = nums[0], result = nums[0];
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] < 0) {
            int temp = maxProd;
            maxProd = minProd;
            minProd = temp;
        }
        maxProd = (nums[i] > maxProd * nums[i]) ? nums[i] : maxProd * nums[i];
        minProd = (nums[i] < minProd * nums[i]) ? nums[i] : minProd * nums[i];
        if (maxProd > result) result = maxProd;
    }
    return result;
}
    

This code finds the maximum product of any contiguous subarray in the input array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single loop that goes through each element of the array once.
• How many times: The loop runs exactly once for each element, so n times where n is the array size.

How Execution Grows With Input

As the array size grows, the number of steps grows directly in proportion.

Input Size (n)	Approx. Operations
10	About 10 steps
100	About 100 steps
1000	About 1000 steps

Pattern observation: Doubling the input size roughly doubles the work done.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the maximum product subarray grows linearly with the size of the input array.

Common Mistake

[X] Wrong: "Because there are nested calculations, the time complexity must be quadratic O(n²)."

[OK] Correct: The code only loops once through the array; the calculations inside the loop are constant time, so the total time grows linearly, not quadratically.

Interview Connect

Understanding this linear time solution shows you can handle tricky problems efficiently, a skill that helps in many real-world coding challenges.

Self-Check

"What if we used a nested loop to check every possible subarray product? How would the time complexity change?"