Buy and Sell Stocks All Variants in DSA C - Time & Space Complexity

Time Complexity: Buy and Sell Stocks All Variants

O(n)

Understanding Time Complexity

When solving buy and sell stock problems, we want to know how the time needed changes as the number of days grows.

We ask: How does the number of price checks and decisions grow with more days?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int maxProfit(int* prices, int pricesSize) {
    int minPrice = prices[0];
    int maxProfit = 0;
    for (int i = 1; i < pricesSize; i++) {
        if (prices[i] < minPrice) {
            minPrice = prices[i];
        } else if (prices[i] - minPrice > maxProfit) {
            maxProfit = prices[i] - minPrice;
        }
    }
    return maxProfit;
}
    

This code finds the best single buy and sell day to maximize profit from stock prices over days.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

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

How Execution Grows With Input

As the number of days increases, the code checks each day's price once.

Input Size (n)	Approx. Operations
10	About 9 checks
100	About 99 checks
1000	About 999 checks

Pattern observation: The number of operations grows directly with the number of days.

Final Time Complexity

Time Complexity: O(n)

This means the time needed grows in a straight line with the number of days.

Common Mistake

[X] Wrong: "Checking every pair of buy and sell days is needed to find max profit."

[OK] Correct: This would take much longer, but the smart one-pass method finds the answer by remembering the lowest price so far.

Interview Connect

Understanding how to scan prices once and keep track of key values shows you can write efficient code, a skill interviewers appreciate.

Self-Check

"What if we allowed multiple buy and sell transactions? How would the time complexity change?"