Best Time to Buy and Sell Stock II — Problem & Solution
Best Time to Buy and Sell Stock II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Best Time to Buy and Sell Stock II is a medium coding problem on arrays, dynamic programming and greedy, asked in Directi interviews.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Greedy
- Asked at: Directi
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given prices where prices[i] is a stock's price on day i. You may buy and sell on the same day, holding at most one share at a time, with unlimited transactions.
Return the maximum total profit.
Example 1
Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy day 2, sell day 3 (+4); buy day 4, sell day 5 (+3).
Example 2
Input: prices = [1,2,3,4,5]
Output: 4
Example 3
Input: prices = [7,6,4,3,1]
Output: 0
Constraints
1 <= prices.length <= 300 <= prices[i] <= 1000
Hints for Best Time to Buy and Sell Stock II
Hint 1
Every upward price movement can be captured independently.
Hint 2
Sum all positive day-to-day differences.
How to solve Best Time to Buy and Sell Stock II
With unlimited transactions and same-day trading allowed, there is nothing to plan. Any profitable multi-day hold can be split into its individual daily moves without losing a penny, so the best possible total is simply the sum of every upward step in the price series.
Approach
- Walk the prices from the second day onwards.
- If today's price is higher than yesterday's, add the difference to the total.
- Ignore every day where the price fell or stayed flat.
- The accumulated total is the maximum profit.
Why it works
Two directions. It is achievable: buying at the start of every rising run and selling at its top yields exactly the sum of the positive steps, since a hold from i to j earns prices[j] - prices[i], which telescopes into the daily differences along the way. It is also an upper bound: any set of non-overlapping holds earns the sum of its own telescoped differences, and each of those is at most the sum of the positive steps it covers, because the negative steps only subtract. So the two meet.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- Do not try to find the global minimum and maximum — that solves the single-transaction problem and undercounts here.
- A strictly falling series earns
0, not a negative number: only positive differences are added. - Flat days contribute nothing, so
>versus>=makes no difference to the total.
Reference solution
Python
from typing import List
def maxProfit(prices: List[int]) -> int:
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
profit += prices[i] - prices[i - 1]
return profitJava
public static int maxProfit(int[] prices) {
int total = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) total += prices[i] - prices[i - 1];
}
return total;
}C++
int maxProfit(vector<int>& prices) {
int total = 0;
for (int i = 1; i < (int) prices.size(); i++) {
if (prices[i] > prices[i - 1]) total += prices[i] - prices[i - 1];
}
return total;
}JavaScript
var maxProfit = function(prices) {
let profit = 0;
for (let i = 1; i < prices.length; i++) {
if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1];
}
return profit;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming