121. Best Time to Buy and Sell Stock

Problem Description

The problem presents us with an array named prices that represents the price of a certain stock on each day. Our objective is to choose a single day for buying one stock and another future day for selling that stock in order to achieve the maximum possible profit. If it's not possible to make any profit, the expected return value is 0. This problem essentially asks us to find two days, where buying on the first and selling on the second would result in the highest profit margin.

Intuition

The intuition behind the solution revolves around evaluating the difference between buying and selling prices while also making sure that we buy at the lowest price possible before selling. The strategy is to keep track of two key variables as we iterate through the prices array: the maximum profit found so far and the lowest price observed. We initialize the maximum profit (ans) as 0 and the minimum price (mi) as infinity to simulate that we haven't bought any stock yet.

As we iterate over each price in prices, we consider it as the potential selling price and calculate the profit we would get if we bought at the lowest price seen until now (mi). If this profit is larger than the current maximum profit (ans), we update ans. Regardless of whether it led to a new maximum profit or not, we then update mi if the current price is lower than any we've seen so far.

By the end of the iteration, we will have the highest possible profit that can be made with a single transaction, which is the difference between the lowest purchasing price and the highest subsequent selling price.

Learn more about Dynamic Programming patterns.

Solution Approach

The provided solution uses a simple yet effective approach that relies on a single pass through the prices array, a concept that is often referred to as the "One Pass" algorithm. This algorithm falls under the category of greedy algorithms since it makes a locally optimal choice at each step with the hope of finding a global optimum.

Here's a step-by-step walk-through of the implementation:

Initialize Variables: Two variables are initialized at the start. ans is initialized to 0 to represent the maximum profit which starts at no profit, and mi is set to inf, representing the minimum buying price (set to infinity since we have not encountered any price yet).
Iterate Over prices: We loop through each price v in the array prices, treating each one as a potential selling price.
Calculate Profit and Update Maximum Profit (ans): For each price v, if selling at this price leads to a profit higher than the best profit found so far (ans), the maximum profit is updated. This is done by computing the difference v - mi and using the max function: ans = max(ans, v - mi).
Update Minimum Buying Price (mi): After checking the potential profit at price v, update the minimum buying price if v is lower than all previously seen prices: mi = min(mi, v).
Return Maximum Profit: After finishing the traversal of the array prices, the variable ans holds the maximum profit that can be achieved. This value is returned as the solution to the problem.

The algorithm's efficiency hinges on the fact that the maximum profit can be found by simply keeping track of the lowest price to buy before each potential selling day. It uses constant space (only two variables), and the time complexity is linear, O(n), as it requires only one pass through the list of prices, where n is the number of prices in the input array.

This approach comes under dynamic programming as well since it essentially keeps a running track of state (in this case, the minimum element so far and the maximum profit so far), but it is the greedy aspect of choosing the current best action (buy/sell) that defines it more aptly.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's assume we have an array of stock prices for 5 consecutive days, represented as follows: prices = [7, 1, 5, 3, 6, 4].

Applying the solution approach step-by-step:

Initialize Variables: Set ans = 0 (maximum profit starts at no profit) and mi = inf (minimum buying price is initially set to infinity since no prices have been seen yet).
Iterate Over prices Day 1 (prices[0] = 7): Start with the first price. Since mi is set to infinity, any price we encounter will be lower, so we set mi = 7.
Day 2 (prices[1] = 1): Proceed to the next price.
- Potential profit if we sell today: 1 - mi = 1 - 7 = -6. Since this is negative, no profit is made. We don't update ans.
- Update mi since 1 is less than 7: mi = 1.
Day 3 (prices[2] = 5): Move on to the third price.
- Potential profit: 5 - mi = 5 - 1 = 4. This is a profit, and since ans is 0, it becomes the new maximum profit: ans = 4.
- mi remains at 1, as 5 is higher than the current mi.
Day 4 (prices[3] = 3): Evaluating the fourth price.
- Potential profit: 3 - mi = 3 - 1 = 2. This is less than the current ans of 4, so ans remains unchanged.
- Update mi to 3? No, since 3 is more than the current mi of 1.

Day 4 (prices[3] = 3) 6. Day 5 (prices[4] = 6): Analyzing the fifth price.

Potential profit: 6 - mi = 6 - 1 = 5. This exceeds the current ans of 4, so we update ans = 5.
mi remains unchanged as 6 is higher than 1.

Day 6 (prices[5] = 4): Finally, the price on the last day.
- Potential profit: 4 - mi = 4 - 1 = 3. This does not beat the current ans of 5, so ans stays at 5.
- mi does not change, as 4 is higher than 1.
Return Maximum Profit: Having processed all days, we have found that the maximum profit is ans = 5, which is the highest profit achievable (by buying on day 2 at a price of 1 and selling on day 5 at a price of 6).

The solution approach efficiently found the best day to buy and the best day to sell in a single pass through the prices array, confirming the maximum profit of 5 for this example. The linear time complexity (O(n)) and constant space complexity are apparent, as the algorithm only needed to iterate through the array once while using two variables.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxProfit(self, prices: List[int]) -> int:
5        # Initialize the maximum profit to 0
6        max_profit = 0
7        # Initialize the minimum price to infinity
8        min_price = float('inf')
9      
10        # Loop through the prices
11        for price in prices:
12            # Update the maximum profit if the current price minus the minimum price seen so far is greater
13            max_profit = max(max_profit, price - min_price)
14            # Update the minimum price seen so far if the current price is lower
15            min_price = min(min_price, price)
16          
17        # Return the maximum profit achieved
18        return max_profit
19

1class Solution {
2    public int maxProfit(int[] prices) {
3        // Initialize 'maxProfit' to 0, which is the minimum profit that can be made.
4        int maxProfit = 0;
5
6        // Assume the first price is the minimum buying price.
7        int minPrice = prices[0];
8      
9        // Loop through all the prices to find the maximum profit.
10        for (int price : prices) {
11            // Calculate the maximum profit by comparing the current 'maxProfit'
12            // with the difference of the current price and the 'minPrice'.
13            maxProfit = Math.max(maxProfit, price - minPrice);
14          
15            // Update the 'minPrice' if a lower price is found.
16            minPrice = Math.min(minPrice, price);
17        }
18      
19        // Return the maximum profit that can be achieved.
20        return maxProfit;
21    }
22}
23

1#include <vector>
2#include <algorithm> // Include algorithm header for the min and max functions
3
4class Solution {
5public:
6    int maxProfit(vector<int>& prices) {
7        int max_profit = 0;   // Variable to store the calculated maximum profit
8        int min_price = prices[0]; // Initialize the minimum price to the first price
9
10        // Loop through all the prices
11        for (int price : prices) {
12            // Update max_profit if the difference between current price and min_price is greater than current max_profit
13            max_profit = max(max_profit, price - min_price);
14          
15            // Update min_price if the current price is less than the current min_price
16            min_price = min(min_price, price);
17        }
18      
19        return max_profit; // Return the calculated maximum profit
20    }
21};
22

1function maxProfit(prices: number[]): number {
2    // Initialize the maximum profit as 0, since the minimum profit we can get is 0
3    let maxProfit = 0;
4    // Initialize the minimum price to the first price in the array
5    let minPrice = prices[0];
6  
7    // Loop through each price in the array of prices
8    for (const price of prices) {
9        // Update maxProfit to the higher value between the existing maxProfit and
10        // the profit we get by selling at the current price minus the minPrice
11        maxProfit = Math.max(maxProfit, price - minPrice);
12        // Update minPrice to be the lower between the current minPrice and the current price
13        minPrice = Math.min(minPrice, price);
14    }
15  
16    // Return the maximum profit that can be achieved
17    return maxProfit;
18}
19

Time and Space Complexity

The time complexity of the given function is O(n), where n is the length of the input list prices. This is because the function includes a single loop that iterates through each element in the list exactly once, performing a constant amount of work at each step; thus, the total work done is linear in the size of the input.

The space complexity of the function is O(1), indicating that the amount of additional memory used by the function does not depend on the size of the input. The function only uses a fixed number of extra variables (ans and mi), which require a constant amount of space regardless of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10]

[100, 33, 30]

[10, 12, 20]

I don't know