Stock Buy and Sell

Hero Image

Problem Overview

The problem is a classic question in stock trading optimizations, titled "Best Time to Buy and Sell Stock." It is categorized under the topic of Arrays on LeetCode. The task is to determine the maximum profit achievable from a given array representing the daily price of a stock. You are only allowed to make one purchase and one sale.

LeetCode URL: Best Time to Buy and Sell Stock

The problem requires you to optimize your trading strategy to maximize profit and considers real-world constraints like buying the stock before selling it.

Understanding the Problem

Given an array prices where prices[i] is the price of a stock on the ith day, you need to compute the maximum profit you can achieve by completing exactly one purchase followed by one sale. If no profit can be made, return 0.

Example

Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6 - 1 = 5.

This example clarifies that you must look for the lowest price to buy and the highest subsequent price to sell for the maximum profit.

Key DSA Concepts and Theory

Arrays

Arrays are a basic data structure where you'll store the daily prices of the stock. They allow efficient access and iteration over elements, which is essential for comparing and computing potential profits on different days.

Single Pass Algorithm

A single pass algorithm involves going through the array once to solve the problem. It is optimal for problems needing linear time solutions, as double iteration (nested loops) would increase time complexity significantly.

Dynamic Programming Approach

A useful approach here is using a dynamic programming-like technique, maintaining the minimum price observed so far and calculating the potential profit at every step.

Solution Approach

Step-by-Step Solution

To solve this problem, we can loop through the given array, keeping track of the lowest price encountered so far and computing the potential profit at each step. Here’s how you can achieve this:

  1. Initialize Variables:

    • Create a variable min_price and set it to a large value (infinity).
    • Create a variable max_profit and set it to 0.
  2. Iterate through the Array:

    • For each price in the array:
      • Update min_price to be the minimum of min_price and the current price.
      • Calculate the profit if you sell at the current price: current_profit = price - min_price.
      • Update max_profit to be the maximum of itself and current_profit.
  3. Return the Result:

    • After completing the loop, max_profit holds the maximum profit possible.

C++ Code Implementation

#include <vector>
#include <algorithm>
#include <limits.h>

class Solution {
public:
    int maxProfit(std::vector<int>& prices) {
        int min_price = INT_MAX;
        int max_profit = 0;
        
        for (int price : prices) {
            min_price = std::min(min_price, price);
            int current_profit = price - min_price;
            max_profit = std::max(max_profit, current_profit);
        }
        
        return max_profit;
    }
};

Java Code Implementation

class Solution {
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxProfit = 0;
        
        for (int price : prices) {
            if (price < minPrice) {
                minPrice = price;
            } else if (price - minPrice > maxProfit) {
                maxProfit = price - minPrice;
            }
        }
        
        return maxProfit;
    }
}

Time and Space Complexity Analysis

Time Complexity:

  • The solution runs in O(n) time, where n is the number of days (length of the prices array). This is because we iterate through the array once.

Space Complexity:

  • The space complexity is O(1), as no additional space proportional to input size is required; only a few variables are used for tracking the calculations.

Common Mistakes to Avoid

  • Ignoring Negative Profits: Make sure to handle cases where buying a stock after selling results in a negative profit. By initializing max_profit to 0, you ensure that if no profit is possible, the function returns 0.
  • Incorrect Tracking of Minimum Price: Updating min_price should always reflect the lowest value encountered up to the current day.

Similar Problems on LeetCode

  1. Best Time to Buy and Sell Stock II (LeetCode 122)
  2. Best Time to Buy and Sell Stock III (LeetCode 123)
  3. Best Time to Buy and Sell Stock with Cooldown (LeetCode 309)
  4. Maximum Subarray (LeetCode 53)

Additional Resources and References

This article should provide you with a comprehensive understanding of how to tackle the "Best Time to Buy and Sell Stock" problem on LeetCode using efficient algorithms and concepts.