Buy and Sell Stocks All Variants in DSA Go

Mental Model

We want to find the best times to buy and sell stocks to make the most money. The key is to track prices and decide when to buy low and sell high.

Analogy: Imagine you are at a fruit market where prices change every day. You want to buy fruit when it's cheap and sell it when the price goes up to make a profit.

Day:    0    1    2    3    4    5
Price:  7 ->  1 ->  5 ->  3 ->  6 ->  4 -> null
        ↑
      start

Dry Run Walkthrough

Input: prices: [7, 1, 5, 3, 6, 4], max 1 transaction

Goal: Find the best single buy and sell to maximize profit

Step 1: Set min_price to 7 (day 0), max_profit to 0

min_price=7, max_profit=0

Why: Start tracking the lowest price and profit

Step 2: Check price 1 (day 1), update min_price to 1

min_price=1, max_profit=0

Why: Found a cheaper price to buy

Step 3: Check price 5 (day 2), profit = 5 - 1 = 4, update max_profit to 4

min_price=1, max_profit=4

Why: Selling now yields better profit

Step 4: Check price 3 (day 3), profit = 3 - 1 = 2, max_profit stays 4

min_price=1, max_profit=4

Why: Profit less than max, no update

Step 5: Check price 6 (day 4), profit = 6 - 1 = 5, update max_profit to 5

min_price=1, max_profit=5

Why: Better profit found

Step 6: Check price 4 (day 5), profit = 4 - 1 = 3, max_profit stays 5

min_price=1, max_profit=5

Why: Profit less than max, no update

Result:

max_profit=5

Annotated Code

DSA Go

package main

import "fmt"

// maxProfitSingleTransaction finds max profit with one buy and one sell
func maxProfitSingleTransaction(prices []int) int {
    minPrice := int(^uint(0) >> 1) // max int
    maxProfit := 0
    for _, price := range prices {
        if price < minPrice {
            minPrice = price // update min price to buy
        } else if profit := price - minPrice; profit > maxProfit {
            maxProfit = profit // update max profit if selling now is better
        }
    }
    return maxProfit
}

func main() {
    prices := []int{7, 1, 5, 3, 6, 4}
    fmt.Println(maxProfitSingleTransaction(prices))
}

minPrice := int(^uint(0) >> 1) // max int

initialize minPrice to a very large number to find minimum

for _, price := range prices {

iterate over each price to check buy/sell opportunities

if price < minPrice { minPrice = price }

update minPrice when a lower price is found

else if profit := price - minPrice; profit > maxProfit { maxProfit = profit }

calculate profit and update maxProfit if better

Output

5

Complexity Analysis

Time: O(n) because we scan the price list once

Space: O(1) because we use only a few variables

vs Alternative: Naive approach checks all pairs (O(n^2)), this is much faster

Edge Cases

empty price list

returns 0 profit because no transactions possible

DSA Go

for _, price := range prices {

prices always decreasing

returns 0 profit because no profitable transaction

DSA Go

else if profit := price - minPrice; profit > maxProfit {

single day price

returns 0 profit because cannot sell after buying

DSA Go

for _, price := range prices {

When to Use This Pattern

When asked to maximize profit from stock prices with buy/sell constraints, use tracking min price and max profit to solve efficiently.

Common Mistakes

Mistake: Updating max profit before updating min price causes wrong profit calculation
Fix: Always update min price first if current price is lower, then calculate profit

Summary

Finds the best single buy and sell day to maximize stock profit.

Use when you want max profit from one transaction in a price list.

Track the lowest price so far and update max profit by selling at current price.

Practice

1. What is the main goal when solving the Buy and Sell Stocks problem variants?

easy

A. Find the day with the highest stock price only

B. Minimize the number of transactions regardless of profit

C. Maximize the profit by choosing the best days to buy and sell stocks

D. Calculate the average stock price over all days

Solution

1. Step 1: Understand the problem goal

   The problem asks to maximize profit by buying and selling stocks on certain days.

2. Step 2: Identify the correct objective

   Maximizing profit means choosing days to buy low and sell high, not just counting transactions or prices.

3. Final Answer:

   Maximize the profit by choosing the best days to buy and sell stocks -> Option C

4. Quick Check:

   Goal = Maximize profit [OK]

Hint: Focus on profit maximization, not just prices or counts [OK]

Common Mistakes:

• Confusing profit with number of transactions
• Thinking only about highest price day
• Ignoring the buy day in calculations

2. Which of the following Go code snippets correctly initializes a slice to store stock prices for 5 days?

easy

A. prices := []int{7, 1, 5, 3, 6}

B. prices := [5]int{7, 1, 5, 3, 6}

C. prices := make([]int, 5, 5)

D. prices := new([]int{7, 1, 5, 3, 6})

Solution

1. Step 1: Understand slice initialization in Go

   To create a slice with values, use the literal syntax: []int{values}.

2. Step 2: Check each option

   prices := []int{7, 1, 5, 3, 6} correctly creates a slice with given values. prices := [5]int{7, 1, 5, 3, 6} creates an array, not a slice. prices := make([]int, 5, 5) creates an empty slice of length 5 but no values. prices := new([]int{7, 1, 5, 3, 6}) is invalid syntax.

3. Final Answer:

   prices := []int{7, 1, 5, 3, 6} -> Option A

4. Quick Check:

   Slice literal = []int{values} [OK]

Hint: Use []int{...} to create slices with values directly [OK]

Common Mistakes:

• Using array syntax instead of slice
• Using new() incorrectly for slices
• Creating empty slices without values

3. What is the output of the following Go code that finds the max profit with only one transaction?

func maxProfit(prices []int) int {
    minPrice := prices[0]
    maxProfit := 0
    for _, price := range prices {
        if price < minPrice {
            minPrice = price
        } else if price - minPrice > maxProfit {
            maxProfit = price - minPrice
        }
    }
    return maxProfit
}

fmt.Println(maxProfit([]int{7,1,5,3,6,4}))

medium

A. 5

B. 6

C. 4

D. 7

Solution

1. Step 1: Trace the loop to find minPrice and maxProfit

   Start minPrice=7, maxProfit=0. Iterate prices: - price=7: minPrice=7, maxProfit=0 - price=1: minPrice=1 (lower) - price=5: profit=5-1=4 >0, maxProfit=4 - price=3: profit=3-1=2 <4, maxProfit=4 - price=6: profit=6-1=5 >4, maxProfit=5 - price=4: profit=4-1=3 <5, maxProfit=5

2. Step 2: Return maxProfit

   maxProfit is 5 after loop ends.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Max profit = 5 [OK]

Hint: Track min price and update max profit during iteration [OK]

Common Mistakes:

• Not updating minPrice correctly
• Calculating profit before updating minPrice
• Returning wrong variable

4. Identify the bug in this Go function that tries to calculate max profit with unlimited transactions:

func maxProfit(prices []int) int {
    profit := 0
    for i := 0; i < len(prices); i++ {
        if prices[i] > prices[i-1] {
            profit += prices[i] - prices[i-1]
        }
    }
    return profit
}

medium

A. prices slice is not initialized

B. Incorrect profit calculation logic

C. Missing return statement

D. Index out of range error due to accessing prices[i-1] when i=0

Solution

1. Step 1: Check loop and index usage

   The loop starts at i=0, but code accesses prices[i-1], which is prices[-1] at i=0, causing index out of range error.

2. Step 2: Identify fix

   Start loop from i=1 to avoid negative index access.

3. Final Answer:

   Index out of range error due to accessing prices[i-1] when i=0 -> Option D

4. Quick Check:

   Loop index must start at 1 to avoid error [OK]

Hint: Avoid negative indices by starting loop at 1 [OK]

Common Mistakes:

• Starting loop at 0 but accessing i-1
• Ignoring runtime errors
• Not testing with small input arrays

5. Given the prices [3, 3, 5, 0, 0, 3, 1, 4], what is the maximum profit with at most two transactions?

hard

A. 7

B. 6

C. 5

D. 8

Solution

1. Step 1: Understand two transactions limit

   We can buy and sell stocks at most twice to maximize profit.

2. Step 2: Calculate max profit with two transactions

   First transaction: buy at 3, sell at 5 (profit 2) Second transaction: buy at 0, sell at 4 (profit 4) Total profit = 2 + 4 = 6

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Two transactions max profit = 6 [OK]

Hint: Split array, find max profit left and right, sum max [OK]

Common Mistakes:

• Counting overlapping transactions
• Ignoring zero price days
• Calculating only one transaction profit