You are given an integer array prices where prices[i] is the price of a given stock on the ith day.
On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.
Find and return the maximum profit you can achieve.
Example 1:
Input: prices = [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3. Total profit is 4 + 3 = 7.
Example 2:
Input: prices = [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Total profit is 4.
Example 3:
Input: prices = [7,6,4,3,1] Output: 0 Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.
Constraints:
1 <= prices.length <= 3 * 1040 <= prices[i] <= 104#122 Best Time to Buy and Sell Stock II asks you to maximize profit from stock prices when multiple transactions are allowed, but you cannot hold more than one stock at a time. The key observation is that profit can be captured whenever the price increases from one day to the next.
A common greedy approach adds every positive difference between consecutive prices. If prices[i] > prices[i-1], the increase can be treated as a buy on the previous day and a sell on the current day. This works because combining all profitable upward movements yields the same maximum profit as trying to find longer optimal ranges.
Another way to reason about the problem is using dynamic programming with two states: holding a stock and not holding a stock. At each step, you update these states based on whether you buy, sell, or skip.
The greedy method achieves O(n) time with O(1) space, making it the most efficient solution for interview settings.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy (sum of positive price differences) | O(n) | O(1) |
| Dynamic Programming (buy/sell states) | O(n) | O(1) |
NeetCode
The Peak-Valley Approach aims to identify opportunities where a buy (at a valley) and a sell (at a peak) transaction yields profit. The idea is to take advantage of every upward trend between valleys and peaks and sum up the differences.
Time Complexity: O(n), where n is the number of prices.
Space Complexity: O(1), no additional space is used.
1#include <stdio.h>
2
3int maxProfit(int* prices, int pricesSize) {
4 int profit = 0;
5 for
The code iterates over the price array. Whenever a profit opportunity is identified (when today's price is higher than yesterday's), the difference is added to the total profit. This maximizes profit by summing up all 'up-hill' gains directly.
The simple one-pass greedy approach makes a decision on each day based on whether the price will go up (buy or hold) or down (sell or do nothing). This maximizes profit by keeping solutions simple, efficient and using the greedy approach to sum up all local gains.
Time Complexity: O(n)
Space Complexity: O(1)
1public
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of the stock buy-and-sell problems frequently appear in FAANG and other top tech interviews. They test understanding of greedy thinking, dynamic programming concepts, and the ability to simplify complex decision processes.
Only an array is needed to store the daily stock prices. The algorithm processes the array sequentially and maintains minimal variables, making it very space efficient.
The optimal approach is a greedy strategy that adds every positive difference between consecutive prices. This effectively captures all profitable opportunities while keeping the algorithm simple and efficient with linear time complexity.
The greedy approach works because multiple smaller profitable trades produce the same total profit as holding through the entire increasing sequence. By summing all positive daily gains, you ensure no profitable movement is missed.
This solution applies a simple one-pass through the price list, capturing the upswing value each time prices rise day-over-day and summing these gains into total profit output.