Buy and Sell Stock

Maximize Stock Trading Profit. You are given a sequence of stock prices representing the value of a particular stock on consecutive days. You can complete as many transactions as you like with the following constraints:

You must buy before you sell.
You cannot buy on one day and sell on the same day (buying and selling in the same day counts as nothing).

Maximize your profit given these conditions.

For example, consider the following stock prices over a week: 1, 2, 3, 4, 5. If you buy on day 1 and sell on day 5, your profit will be 4 (buy at 1 and sell at 5).

Examples


stock_prices = [7, 1, 5, 3, 6, 4]
output: 7 (Buy on day 2 at 1, sell on day 3 at 5, buy on day 4 at 3, and sell on day 5 at 6)

stock_prices = [1, 2, 3, 4, 5]
output: 4 (Buy on day 1 at 1 and sell on day 5 at 5)

stock_prices = [7, 6, 4, 3, 1]
output: 0 (No transaction is done, i.e., max profit = 0)

stock_prices = [1, 10, 2, 3]
output: 9 (Buy on day 1 at 1 and sell on day 2 at 10)

The goal of this solution is to maximize profit by buying and selling stocks on different days, given an array of stock prices where each element represents the price of the stock on a particular day.

The algorithm uses a greedy approach with a min-heap (implemented as a priority queue) to keep track of the lowest prices encountered so far. By maintaining a collection of potential buy prices, we can ensure that we always buy at the lowest possible price and sell at a higher price later, thereby maximizing profit.

Here's a step-by-step explanation of the approach:

Initialize Data Structures: Use a priority queue (options) to act as a min-heap to store the prices of stocks. Initialize currentProfit to 0, which will store the accumulated profit.
Iterate Through the Stock Prices: For each price in the stockPrices array:
- If the current price is higher than the lowest price in the heap (options.peek()), compute the profit by selling at the current price and buying at the lowest price. Update currentProfit accordingly.
- Remove the lowest price from the heap after using it for profit calculation.
- Push the current price into the heap as a potential buy price.
Return the Total Profit: After iterating through all the prices, return the accumulated currentProfit.

This approach ensures that we always buy low and sell high, using the min-heap to efficiently manage and access the lowest prices encountered.

import heapq

def max_profit_greedy(stock_prices):
    # options will act as a min-heap to store the stock prices encountered so far
    options = []
    # Initialize current_profit to accumulate the total profit
    current_profit = 0

    # Iterate through each price in the list of stock prices
    for price in stock_prices:
        # Check if there is any price in the options and if the current price is higher
        # than the smallest price in the options (heap)
        if len(options) > 0 and price > options[0]:
            # If the condition is true, calculate the profit by subtracting the smallest
            # price in the heap from the current price and add it to current_profit
            current_profit += price - options[0]
            # Remove the smallest price from the heap as it has been used to make a profit
            heapq.heappop(options)

        # Push the current price into the heap (options) to consider it for future transactions
        heapq.heappush(options, price)

    # Return the total accumulated profit
    return current_profit

Time Complexity: Inserting a price into the min-heap and removing the smallest price both take O(log n) time, where n is the number of elements in the heap. Since we perform these operations for each of the n prices in the stockPrices array, the overall time complexity is O(n log n).

Space Complexity: The space complexity is dominated by the storage required for the heap. In the worst case, we might store all n prices in the heap, leading to a space complexity of O(n).

Community solutions

💬 Community guidelines

Stay on topic. Use this section for submitting solutions and providing feedback to others.
Be inclusive. Exponent is a diverse community. Please respect others' opinions and beliefs.

How would you answer? Submit your response below and get feedback from the community.

Laksitha R.

Member

February 6, 2025

Java

public static int maxProfitGreedy(int[] stockPrices) {
int maxProfit = 0;
for(int i = 1; i < stockPrices.length; i++) {
int todayPrice = stockPrices[i-1];
int tomorrowPrice = stockPrices[i];
if(tomorrowPrice > todayPrice) {
maxProfit += tomorrowPrice - todayPrice;
}
}
return maxProfit;
}

Reno S.

Member

2.9k

Updated March 12, 2025

✅ Passes all test cases:

Tricky:

stock_prices = [1, 10, 2, 3]

output: 9 (Buy on day 1 at 1 and sell on day 2 at 10)

Swift

func maxProfit(_ stockPrices: [Int]) -> Int {
    var options: [Int] = [] // min-heap
    var currentProfit = 0
    var maxProfit = 0

    for price in stockPrices {

        if let cheapestOption = options.last, cheapestOption < price {
            if currentProfit < price {
                currentProfit += price // greedy profit
            } else {
                currentProfit = price 
            }
            currentProfit -= options.removeLast() // sell cheapest option
            maxProfit = max(maxProfit, currentProfit)
        } 
        options.append(price)
        options.sort { $0 > $1 } // min heap - descending sort
    }
    return maxProfit
}

let testcases = [
    (prices: [7, 1, 5, 3, 6, 4], expected: 7),
    (prices: [1, 2, 3, 4, 5], expected: 4),
    (prices: [7, 6, 4, 3, 1], expected: 0),
    (prices: [1, 10, 2, 3], expected: 9),
    (prices: [], expected: 0),
    (prices: [1, 2, 3, 4], expected: 3),
    (prices: [4, 3, 2, 1], expected: 0),
    (prices: [1, 10, 2, 1], expected: 9),
    (prices: [1], expected: 0),
]

for test in testcases {
    let actual = maxProfit(test.prices)
    print(test.expected == actual ? "PASS" : "FAIL, Expected:\(test.expected), Got:\(actual)") 
}

Prajwal M.

Member

189

May 29, 2025

Python

from typing import List

def max_profit_greedy(stock_prices: List[int]) -> int:
    l=0 # buying 
    r=1 # selling
    max_profit=0
    while r<len(stock_prices):
        if stock_prices[r]>stock_prices[l]:
            profit=stock_prices[r]-stock_prices[l]
            max_profit=max(max_profit,profit)
        else:
            l=r
        r+=1

    return max_profit

# debug your code below
print(max_profit_greedy([7, 1, 5, 3, 6, 4]))

Tiago R.148

November 7, 2024

I didn't even use a heap. Not sure if there's a gap in my greedy solution but seems it works this way being O(n):

JavaScript

function maxProfitGreedy(stockPrices) {
    let minPrice = stockPrices[0];
    let maxPrice = -Infinity;
    let previousStock = -Infinity;
    let profit = 0;

    for (let stock of stockPrices) {
        if (previousStock > stock && maxPrice !== -Infinity) {
            profit += maxPrice - minPrice;
            maxPrice = -Infinity;
            minPrice = stock;
        }
        else {
            if (stock > maxPrice) {
                maxPrice = stock;
            } 
            if (stock < minPrice) {
                minPrice = stock;
            }       
        }
        previousStock = stock;
    }
    if (maxPrice !== -Infinity && maxPrice !== minPrice) {
        profit += maxPrice - minPrice;
    }

    return profit;
}

See community answers

ML Engineer Introduction

ML System Design Questions

Overview

Mock Interviews & Practice Questions

ML Concepts Questions

Overview

Model & Algorithm Fundamentals

Mock Interviews

ML Coding Questions

Overview

Mock Interviews & Practice Questions

Software Engineering Coding Questions

Overview

Fast Track

Time & Space Complexity

Coding Patterns

Arrays

Hash Tables

Searching & Sorting

String Manipulation

Graphs

Trees

Stacks & Queues

Linked Lists

Heaps

Recursion & Backtracking

Dynamic Programming

Behavioral Interviews: A Practical Guide for Engineers

Fast Track (Start Here)

Theory

Tactics

Mock Interviews & Analyses

Practice

ML Engineer Introduction

ML System Design Questions

Overview

Mock Interviews & Practice Questions

ML Concepts Questions

Overview

Model & Algorithm Fundamentals

Mock Interviews

ML Coding Questions

Overview

Mock Interviews & Practice Questions

Software Engineering Coding Questions

Overview

Fast Track

Time & Space Complexity

Coding Patterns

Arrays

Hash Tables

Searching & Sorting

String Manipulation

Graphs

Trees

Stacks & Queues

Linked Lists

Heaps

Recursion & Backtracking

Dynamic Programming

Behavioral Interviews: A Practical Guide for Engineers

Fast Track (Start Here)

Theory

Tactics

Mock Interviews & Analyses

Practice

Buy and Sell Stock

Examples