Best Time to Buy and Sell Stock

Sliding WindowArray

15 min

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example

Example 1:

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

Day 1

Day 2

Day 3

Day 4

Day 5

Day 6

Max Profit: 5

(Buy on Day 2, Sell on Day 5)

Output: 5

Solution

This problem can be solved efficiently using a sliding window approach. We use two pointers, `left` (buy) and `right` (sell), to represent the current window of transactions. We iterate through the prices, updating the maximum profit found so far.

Algorithm Steps

Initialize `left` pointer to 0, `right` pointer to 1, and `maxProfit` to 0.
Iterate with the `right` pointer through the `prices` array.
If `prices[right]` is greater than `prices[left]`, calculate the potential profit. Update `maxProfit` if this profit is higher.
If `prices[right]` is less than or equal to `prices[left]`, it means we've found a new potential buying point. Move the `left` pointer to the `right` pointer's position.
Increment the `right` pointer in each iteration to expand the window.
Return `maxProfit` after the loop finishes.

Best Time to Buy and Sell Stock

Sliding Window Approach

Progress1 / 1

Ready to start the visualization

Stock Prices

Buy

Sell

Current Profit

Max Profit

Best Time to Buy and Sell Stock Solution


class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        l, r = 0, 1 # left=buy, right=sell
        maxP = 0

        while r < len(prices):
            # profitable?
            if prices[l] < prices[r]:
                profit = prices[r] - prices[l]
                maxP = max(maxP, profit)
            else:
                l = r
            r += 1
        return maxP