121. Best Time to Buy and Sell Stock

EasyArrayDynamic Programming
Leetcode Link

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

Which type of traversal does breadth first search do?

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:

  1. 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).

  2. Iterate Over prices: We loop through each price v in the array prices, treating each one as a potential selling price.

  3. 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).

  4. 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).

  5. 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.

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

Which of these properties could exist for a graph but not a tree?

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:

  1. 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).

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  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.

  2. 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
Not Sure What to Study? Take the 2-min Quiz

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«