Python – Determine the Best Time to Buy and Sell Stock using an Array

This tutorial will help you solve a common interview problem: determining the best time to buy and sell stock to maximize profit. Using an array where each element represents the stock price on a given day, we’ll walk through the problem statement, sample inputs and outputs, solution steps, and a complete Python program.

Problem Statement

Given an array prices where each element represents the stock price on a specific day, find the maximum profit achievable by buying one stock and selling it later. You must buy before you sell. If no profit is possible, return 0.

Sample Input and Output

Example 1:

</>
Copy
Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5

Explanation:
Buy on day 2 (price = 1) and sell on day 5 (price = 6), resulting in a profit of 6 - 1 = 5.

Example 2:

</>
Copy
Input: prices = [7, 6, 4, 3, 1]
Output: 0

Explanation:
Prices are in descending order, so no profit can be made.

Solution Approach

We can solve this problem with an efficient single-pass algorithm by following these steps:

  1. Initialize min_price with a very high value (infinity) and max_profit with 0.
  2. Iterate through each price in the array.
  3. For each price, update min_price if the current price is lower than the previously recorded min_price.
  4. Calculate the potential profit by subtracting min_price from the current price.
  5. If the calculated profit is greater than max_profit, update max_profit.
  6. Return max_profit after the loop ends, which represents the maximum profit achievable.

Python Program

</>
Copy
# Function to calculate the maximum profit from stock prices
def max_profit(prices):
    # Initialize the minimum price to a very high value and max profit to 0
    min_price = float('inf')
    max_profit = 0

    # Iterate through each price in the list
    for price in prices:
        # Update the minimum price if the current price is lower
        if price < min_price:
            min_price = price
        # Calculate the potential profit for the current price
        profit = price - min_price
        # Update max_profit if the current profit is higher
        if profit > max_profit:
            max_profit = profit
    return max_profit

# Test the function with sample inputs

# Example 1
prices1 = [7, 1, 5, 3, 6, 4]
print("Maximum Profit for Example 1:", max_profit(prices1))  # Expected Output: 5

# Example 2
prices2 = [7, 6, 4, 3, 1]
print("Maximum Profit for Example 2:", max_profit(prices2))  # Expected Output: 0

The above Python program efficiently computes the maximum profit by tracking the minimum price encountered so far and updating the profit accordingly. This approach runs in O(n) time and uses O(1) extra space, making it ideal for coding interviews.

Conclusion

In this tutorial, we discussed how to determine the best time to buy and sell stock using an array. We covered the problem statement, provided sample inputs and outputs, explained the solution steps in detail, and presented a complete Python program to solve the problem.