Bird
Raised Fist0
DSA C++programming~5 mins

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

Choose your learning style10 modes available
LearnWhyDeepVisualTryChallengeProjectRecallTime
Time Complexity: Buy and Sell Stocks All Variants
O(n)
Understanding Time Complexity

We want to understand how the time needed to find the best buy and sell days changes as the number of stock prices grows.

How does the work increase when we have more days of prices?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.


int maxProfit(const std::vector<int>& prices) {
    int minPrice = INT_MAX;
    int maxProfit = 0;
    for (int price : prices) {
        if (price < minPrice) {
            minPrice = price;
        } else if (price - minPrice > maxProfit) {
            maxProfit = price - minPrice;
        }
    }
    return maxProfit;
}

This code finds the maximum profit from buying and selling once by scanning prices once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

  • Primary operation: One loop that goes through each price once.
  • How many times: Exactly once for each price in the list.
How Execution Grows With Input

As the number of days increases, the work grows directly in proportion.

Input Size (n)Approx. Operations
10About 10 checks and updates
100About 100 checks and updates
1000About 1000 checks and updates

Pattern observation: Doubling the input roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the best buy and sell days grows linearly with the number of prices.

Common Mistake

[X] Wrong: "We need to check every pair of days, so it must be O(nĀ²)."

[OK] Correct: This code smartly tracks the lowest price so far and calculates profit on the fly, avoiding checking all pairs.

Interview Connect

Understanding this linear approach shows you can find efficient solutions by avoiding unnecessary repeated work, a key skill in interviews.

Self-Check

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

Practice

(1/5)
1. What is the main goal when solving the Buy and Sell Stocks problem with only one transaction allowed?
easy
A. Sell before buying to maximize profit
B. Minimize the buying price regardless of selling price
C. Buy and sell on the same day to avoid loss
D. Maximize the difference between a later selling price and an earlier buying price

Solution

  1. Step 1: Understand the problem constraints

    The problem allows only one buy and one sell, so the goal is to find the maximum profit from one pair of days where buying day is before selling day.

  2. Step 2: Identify the profit calculation

    Profit = selling price - buying price. We want to maximize this difference with the buying day before selling day.

  3. Final Answer:

    Maximize the difference between a later selling price and an earlier buying price -> Option D

  4. Quick Check:

    Profit = sell price - buy price [OK]
Hint: Find max difference with buy day before sell day [OK]
Common Mistakes:
  • Ignoring the order of buy and sell days
  • Trying to minimize price without considering selling
  • Assuming multiple transactions allowed
2. Which of the following C++ code snippets correctly initializes a vector of stock prices for the Buy and Sell Stocks problem?
easy
A. std::vector prices = (7, 1, 5, 3, 6, 4);
B. std::vector<int> prices = {7, 1, 5, 3, 6, 4};
C. vector prices = [7, 1, 5, 3, 6, 4];
D. std::vector<int> prices = (7, 1, 5, 3, 6, 4);

Solution

  1. Step 1: Recall correct vector initialization syntax

    In C++, a vector of integers is initialized with curly braces and type specified: std::vector<int> prices = {values};

  2. Step 2: Check each option

    std::vector<int> prices = {7, 1, 5, 3, 6, 4}; uses correct syntax with std::vector<int> and curly braces. Options A, B, and D use incorrect syntax for vector initialization.

  3. Final Answer:

    std::vector<int> prices = {7, 1, 5, 3, 6, 4}; -> Option B

  4. Quick Check:

    Use std::vector<int> and braces {} [OK]
Hint: Use std::vector<int> and curly braces {} to initialize [OK]
Common Mistakes:
  • Using square brackets [] instead of curly braces {}
  • Omitting the type <int>
  • Using parentheses () instead of braces
3. What is the output of the following C++ code that finds the maximum profit with unlimited transactions allowed? 
std::vector<int> prices = {7, 1, 5, 3, 6, 4};
int maxProfit = 0;
for (int i = 1; i < prices.size(); i++) {
    if (prices[i] > prices[i - 1]) {
        maxProfit += prices[i] - prices[i - 1];
    }
}
std::cout << maxProfit << std::endl;
medium
A. 7
B. 5
C. 8
D. 6

Solution

  1. Step 1: Understand the loop and profit calculation

    The code adds profit for every day where price increases from previous day, summing all positive differences.

  2. Step 2: Calculate profits day by day

    Day 1 to 2: 1 - 7 = -6 (no profit)
    Day 2 to 3: 5 - 1 = 4 (add 4)
    Day 3 to 4: 3 - 5 = -2 (no profit)
    Day 4 to 5: 6 - 3 = 3 (add 3)
    Day 5 to 6: 4 - 6 = -2 (no profit)
    Total profit = 4 + 3 = 7

  3. Final Answer:

    7 -> Option A

  4. Quick Check:

    Sum of positive differences = 7 [OK]
Hint: Sum all positive price differences for unlimited transactions [OK]
Common Mistakes:
  • Adding negative differences as profit
  • Only considering one transaction
  • Miscounting indices in loop
4. Identify the bug in this C++ code snippet that tries to find the maximum profit with only one transaction allowed: 
std::vector<int> prices = {7, 1, 5, 3, 6, 4};
int minPrice = INT_MAX;
int maxProfit = 0;
for (int i = 0; i < prices.size(); i++) {
    if (prices[i] < minPrice) {
        minPrice = prices[i];
    } else if (prices[i] - minPrice > maxProfit) {
        maxProfit = prices[i] - minPrice;
    }
}
std::cout << maxProfit << std::endl;
medium
A. No bug, code works correctly
B. minPrice should be initialized to 0
C. maxProfit should be initialized to INT_MIN
D. Loop should start from i = 1 instead of 0

Solution

  1. Step 1: Analyze initialization and loop

    minPrice is set to INT_MAX to find minimum price correctly. maxProfit starts at 0. Loop from 0 to end checks each price.

  2. Step 2: Check logic correctness

    For each price, update minPrice if current price is lower. Else, calculate profit and update maxProfit if higher. This correctly finds max profit with one transaction.

  3. Final Answer:

    No bug, code works correctly -> Option A

  4. Quick Check:

    Correct minPrice and maxProfit updates [OK]
Hint: Initialize minPrice to INT_MAX and loop from 0 [OK]
Common Mistakes:
  • Starting loop from 1 and missing first price
  • Initializing minPrice to 0 causing wrong min
  • Initializing maxProfit to INT_MIN causing negative profits
5. Given the prices {3, 3, 5, 0, 0, 3, 1, 4}, what is the maximum profit achievable with at most two transactions?
hard
A. 5
B. 7
C. 6
D. 8

Solution

  1. Step 1: Understand two transactions limit

    We can buy and sell at most twice. We must find two pairs of buy-sell days maximizing total profit without overlap.

  2. Step 2: Calculate max profit with two transactions

    First transaction: Buy at 3 (day 1), sell at 5 (day 3) profit = 2
    Second transaction: Buy at 0 (day 4), sell at 4 (day 8) profit = 4
    Total profit = 2 + 4 = 6

  3. Final Answer:

    6 -> Option C

  4. Quick Check:

    Sum of two best transactions = 6 [OK]
Hint: Split prices into two parts, sum max profits [OK]
Common Mistakes:
  • Counting overlapping transactions
  • Only considering one transaction
  • Misidentifying buy/sell days
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard