121. Best Time to Buy and Sell Stock
Model: qwen2.5-coder:14b
Topics: Array,Dynamic Programming
FAANG asked: 1
Acceptance rate: 51.8%
Problem Breakdown
The problem asks us to find the maximum profit that can be achieved by buying and selling a stock on different days. The input is an array prices where each element represents the price of the stock on a given day. We need to return the maximum profit possible from a single buy-sell transaction. If no profit can be made, we should return 0.
Inputs:
- An array
pricesof integers representing stock prices over time.
Outputs:
- An integer representing the maximum profit that can be achieved. If no profit is possible, return 0.
Implicit Constraints or Edge Cases:
- The array can have a length between 1 and 10^5.
- Each price in the array is between 0 and 10^4.
- We cannot sell on the same day we buy.
- If prices are in strictly decreasing order, the maximum profit is 0.
Intuition
A brute-force approach would involve checking every possible pair of days to see which one yields the highest profit. This would result in a time complexity of O(n^2), which is inefficient given the constraints.
The key insight is that we can keep track of the minimum price encountered so far and calculate the potential profit for each day by subtracting this minimum price from the current day’s price. By doing this, we ensure that we are always buying at the lowest possible price seen up to that point and selling on the current day.
Approach
- Initialize two variables:
min_priceto a very high value (e.g., infinity) andmax_profitto 0. - Iterate through each price in the array:
- Update
min_priceto be the minimum of the currentmin_priceand the current day’s price. - Calculate the potential profit by subtracting
min_pricefrom the current day’s price. - Update
max_profitto be the maximum of the currentmax_profitand the calculated potential profit.
- Update
- After iterating through all prices, return
max_profit.
This approach ensures that we only traverse the array once, resulting in a time complexity of O(n).
Complexity Analysis
- Time Complexity: O(n), where n is the length of the
pricesarray. We make a single pass through the array. - Space Complexity: O(1). We use a constant amount of extra space for variables.
Solution
def maxProfit(prices):
min_price = float('inf')
max_profit = 0
for price in prices:
min_price = min(min_price, price)
potential_profit = price - min_price
max_profit = max(max_profit, potential_profit)
return max_profit
Edge Cases Handled
- Empty Input: The function will handle an empty input array by returning 0 since
max_profitis initialized to 0. - All Prices Increasing: If the prices are in strictly increasing order, the maximum profit will be the difference between the last and first price.
- All Prices Decreasing: If the prices are in strictly decreasing order, the minimum price will always be updated to the current price, resulting in a
max_profitof 0. - Single Price: If there is only one price in the array, the function will return 0 as no transaction can be made.
The solution provided is correct and efficient. It adheres to the constraints and handles all edge cases appropriately. The time complexity is O(n), which is optimal for this problem, and the space complexity is O(1), as expected.