Grokking 75:Best Time to Buy and Sell Stock

Problem Statement

You are given an array prices where prices[i] is the price of a given stock on the 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.

Examples

- Input: [3, 2, 6, 5, 0, 3]
- Expected Output: 4
- Justification: Buy the stock on day 2 (price = 2) and sell it on day 3 (price = 6). Profit = 6 – 2 = 4.
- Input: [8, 6, 5, 2, 1]
- Expected Output: 0

Justification: Prices are continuously dropping, so no profit can be made.

- Input: [1, 2]
- Expected Output: 1
- Justification: Buy on day 1 (price = 1) and sell on day 2 (price = 2). Profit = 2 – 1 = 1.

Constraints:

1 <= prices.length <= 10⁵
0 <= prices[i] <= 10⁴

Solution

To solve this problem, we iterate through the list of stock prices to find the maximum profit that can be made by buying and selling once. The approach involves keeping track of the lowest price seen so far and calculating the potential profit if the stock were sold at the current price. As we continue to iterate through the prices, we consistently update the minimum price and the maximum profit observed. By the end of the loop, we have determined the highest possible profit that can be achieved from a single buy-sell transaction, ensuring an efficient solution with linear time complexity.

Step-by-Step Algorithm

Initialize Variables:
- Set a variable to hold the minimum price encountered so far to a very high value (initially, the maximum possible integer value).
- Set a variable to hold the maximum profit calculated so far to 0.
Iterate Through Each Price in the Array:
- For each price in the given array:
  - Update the Minimum Price:
    - Compare the current price with the minimum price encountered so far.
    - If the current price is lower, update the minimum price to the current price.
  - Calculate the Potential Profit:
    - Subtract the updated minimum price from the current price to calculate the potential profit if selling at this price.
  - Update the Maximum Profit:
    - Compare the calculated potential profit with the maximum profit recorded so far.
    - If the potential profit is higher, update the maximum profit to this value.
Return the Maximum Profit:
- After completing the iteration through all prices, return the maximum profit calculated.

Algorithm Walkthrough

Consider the input [3, 2, 6, 5, 0, 3]:

Initialize minPrice as infinity and maxProfit as 0.
Iterate through the list:
- Day 1: price is 3
  - minPrice is updated to 3.
  - Profit = 3 - 3 = 0. maxProfit remains 0.
- Day 2: price is 2
  - minPrice is updated to 2.
  - Profit = 2 - 2 = 0. maxProfit remains 0.
- Day 3: price is 6
  - minPrice remains 2.
  - Profit = 6 - 2 = 4. maxProfit is updated to 4.
- Day 4: price is 5
  - minPrice remains 2.
  - Profit = 5 - 2 = 3. maxProfit remains 4.
- Day 5: price is 0
  - minPrice is updated to 0.
  - Profit = 0 - 0 = 0. maxProfit remains 4.
- Day 6: price is 3
  - minPrice remains 0.
  - Profit = 3 - 0 = 3. maxProfit remains 4.
The final maxProfit is 4.

public class Solution {
    public int maxProfit(int[] prices) {
        // Initialize minPrice to the maximum possible integer value
        int minPrice = Integer.MAX_VALUE;
        // Initialize maxProfit to 0
        int maxProfit = 0;
        // Iterate through each price in the prices array
        for (int price : prices) {
            // Update minPrice to be the minimum of minPrice and the current price
            minPrice = Math.min(minPrice, price);
            // Update maxProfit to be the maximum of maxProfit and the difference between the current price and minPrice
            maxProfit = Math.max(maxProfit, price - minPrice);
        }
        // Return the final maxProfit
        return maxProfit;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] example1 = {3, 2, 6, 5, 0, 3};
        int[] example2 = {8, 6, 5, 2, 1};
        int[] example3 = {1, 2};
        System.out.println(solution.maxProfit(example1)); // Output: 4
        System.out.println(solution.maxProfit(example2)); // Output: 0
        System.out.println(solution.maxProfit(example3)); // Output: 1
    }
}

class Solution {
  maxProfit(prices) {
    // Initialize minPrice to Infinity
    let minPrice = Infinity;
    // Initialize maxProfit to 0
    let maxProfit = 0;
    // Iterate through each price in the prices array
    for (let price of prices) {
      // Update minPrice to be the minimum of minPrice and the current price
      minPrice = Math.min(minPrice, price);
      // Update maxProfit to be the maximum of maxProfit and the difference between the current price and minPrice
      maxProfit = Math.max(maxProfit, price - minPrice);
    }
    // Return the final maxProfit
    return maxProfit;
  }
}

// Testing the algorithm
const solution = new Solution();
const example1 = [3, 2, 6, 5, 0, 3];
const example2 = [8, 6, 5, 2, 1];
const example3 = [1, 2];
console.log(solution.maxProfit(example1));  // Output: 4
console.log(solution.maxProfit(example2));  // Output: 0
console.log(solution.maxProfit(example3));  // Output: 1

Complexity Analysis

Time Complexity: O(n), where n is the number of days. This is because the algorithm iterates through the list of prices once, performing constant-time operations for each price.
Space Complexity: O(1), as it uses a constant amount of extra space (two variables to keep track of minPrice and maxProfit).