LeetCode 121: Best time to buy and sell stock - Kadane's Algorithm
Problem : https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
For this problem we need to find the indices i and j, maximising the equation prices[j] - prices[i], given j > i. Lets first approach the brute force solution of this problem.
1. Brute force:
Complexity: O(n^2)
This is pretty straight forward. We iterate through the entire array and for each element we check the difference between the indices larger than the current index.
Code:
1int maxProfit(vector<int>& prices) {
2
3 int maxProfit = 0;
4
5 for(int i = 0; i < prices.size() - 1; i++) {
6 for(int j = i + 1; j < prices.size(); j++) {
7 maxProfit = max(maxProfit, prices[j] - prices[i])
8 }
9 }
10
11 return maxProfit;
12}
2. Array sum approach
Complexity: O(n)
In this solution we calculate 2 arrays. The first which is calculated from left to right, denotes the minimum value in the array until this index from left. Let’s call this array minArray. The second which is calculated from right to left, denotes the maximum value of the array until this index from right. Let’s call this maxArray.
Then to find out the max profit, we maximise maxArray[i] - minArray[i].
Code:
1int maxProfit(vector<int>& prices) {
2
3 int size = prices.size();
4 int maxProfit = 0, leftMin = 10001, rightMax = 0;
5 int minArray[size], maxArray[size];
6
7
8 for(int i = 0; i < size; i++) {
9
10 if(prices[i] < leftMin) leftMin = prices[i];
11 minArray[i] = leftMin;
12
13 if(prices[size - 1 - i] > rightMax) rightMax = prices[size - 1 - i];
14 maxArray[size - 1 - i] = rightMax;
15
16 }
17
18 for(int i = 0; i < size; i++)
19 if(maxArray[i] - minArray[i] > maxProfit)
20 maxProfit = maxArray[i] - minArray[i];
21
22 return maxProfit;
23}
At any index i,
minArray[i] → the minimum stock price from i to the index 0.
maxArray[i] → the maximum stock price from i to the index size - 1.
So at some point, the optimal buy price will be to the left of i and the optimal sell price will be to the right of i. So if we maximise the difference between both the arrays, we get the optimal solution.
3. Kadane’s Algorithm
Complexity: O(n)
This could also represented as the maximum subarray problem. It’s the task of finding a contiguous subarray with the largest sum, with a given one dimensional array. So how are we going to represent the problem?
Let the array prices contain the list of stock prices.
Lets calculate the array x such that
x[i] = 0, when i == 0
x[i] = prices[i] - prices[i - 1], when i!=0
So for an array of size 5, x is calculated as follows:
x[0] = 0
x[1] = prices[1] - prices[0]
x[2] = prices[2] - prices[1]
x[3] = prices[3] - prices[2]
x[4] = prices[4] - prices[3]
x[5] = prices[5] - prices[4]
Let’s consider the indices 1 and 4 as the prices with the maximum difference. Then we need to calculate the sum elements from x[2] to x[4].
x[2] + x[3] + x[4] = prices[2] - prices[1] + prices[3] - prices[2] + prices[4] - prices[3]
cancelling the middle terms we get,
x[2] + x[3] + x[4] = prices[4] - prices[1]
So to find the solution, we need to find the maximum subarray of the array x. We can use Kadane’s algorithm for this problem.
Kadane’s Algorithm for the maximum subarray problem:
In this algorithm, for each index i in the array, we calculate the maximum subarray ending with i. The maximum subarray for index 0 will be the element itself as there is only one element till 0. Then we find the value for the next element using this condition:
maxCurrent = max(a[i], a[i] + maxCurrent)
where,
maxCurrent → max subarray till the current index and
a → array in consideration
So for every iteration from index 1, the max subarray must be either the element itself(subarray size 1), or the element added to the previous max subarray ending at i - 1. We keep track of the maximum value of maxCurrent for each index, which is the solution.
According to the stocks problem statement, the profit should not be negative. If the optimal solution is negative, then we should return 0. So we initialise maxCurrent as 0. Also unlike the maximum subarray problem, when we consider only one element as part of the subarray, the profit is 0 as we can’t buy and sell on the same day.
So considering all this, for this problem we have to choose the maximum of 0 and x[i] + maxCurrent.
maxCurrent = max(0, x[i] + maxCurrent)
Replacing x with prices,
maxCurrent = max(0, prices[i] - prices[i - 1] + maxCurrent)
Code:
1int maxProfit(vector<int>& prices) {
2
3 int maxProfit = 0, maxCurrent = 0;
4
5 for(int i = 1; i < prices.size(); i++){
6 maxCurrent = max(0, maxCurrent + prices[i] - prices[i - 1]);
7 maxProfit = max(maxProfit, maxCurrent);
8 }
9
10 return maxProfit;
11}