Table of Contents
Problem Statement
The problem “Best Time to Buy and Sell Stock” states that you are given an array of prices of length n, where the ith element stores the price of stock on ith day.
If we can make only one transaction, that is, to buy on one day and sell on another upcoming day, what will be the maximum profit earned.
Example
prices[] = {7, 1, 5, 3, 6, 4}
5
Algorithm
If we buy the stock on ith day, the maximum profit is earned by selling the stock on a day between i + 1 to n, such that the day has the maximum price of the stock and that is greater than price[i].
Consider prices = {7, 1, 5, 3, 6, 4}
So, the maximum profit is earned by buying the stock on day 2 and selling it on day 5, the maximum profit earned is 5.
Naive Approach for Best Time to Buy and Sell Stock
The naive approach to implement the above algorithm is to run two nested loops, one for the buying day and another for finding the maximum profit on upcoming days.
Pseudo Code
int maxProfit = -infinity; for (int i = 0; i < n; i++) { int costPrice = price[i]; int max = -infinity; // Finding the maximum stock price greater than costPrice on upcoming days for (int j = i + 1; j < n; j++) { if (prices[j] > costPrice) { max = maximum(max, a[j]); } } int profit = 0; if (max != -infinity) { profit = max - costPrice; } maxProfit = maximum(maxProfit, profit); }
Complexity Analysis
Time Complexity
O(n^2) , because we are using two nested loops for picking up the day to buy and sell the stock. Thus the time complexity is poltnomial.
Space Complexity
O(1), since we are not storign any information regarding each element in any data structure. We have been using only constant space. Thus the space complexity is linear.
where n is the number of elements in the array.
Optimal Approach for Best Time to Buy and Sell Stock
A better approach is to form an array whose ith element stores the maximum value present in prices array from index i + 1 to n. That is, we are precomputing the work done by inner nested loop in naive approach. So that, we can replace the inner nested loop by directly finding the maximum. The precomputation algorithm works in following manner.
- Create an array named maxSP of size equals size of prices array and a variable max and initialize it as the minimum value.
- Start from the last index in prices array.
- If prices[i] is greater than max
- Update max as prices[i] and make maxSP[i] as minimum value
- Else if prices[i] is not greater than max
- Update maxSP[i] = max.
- If prices[i] is greater than max
- After the pre computation, we follow the naive approach and replace the inner nested loop by using the maxSP array that we just created.
Pseudo Code
// Pre computation int max = -infinity; for (int i = n - 1; i >= 0; i--) { if (prices[i] > max) { max = prices[i]; maxSP[i] = -infinity; } else { maxSP[i] = max; } } // Do as in naive approach int maxProfit = -infinity; for (int i = 0; i < n; i++) { int costPrice = prices[i]; // Rather than using a loop to calculate max, we can directly get it from maxSP array int max = maxSP[i]; int profit = 0; if (max != -infinity) { profit = max - costPrice; } maxProfit = maximum(maxProfit, profit); }
Code
Java Code for Best Time to Buy and Sell Stock problem
import java.util.Scanner; class BestTimetoBuyandSellStock { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // Prices array int prices[] = new int[]{7, 1, 5, 3, 6, 4}; // Calculating the max profit int ans = maxProfit(prices, prices.length); // Print the answer System.out.println(ans); } private static int maxProfit(int[] prices, int n) { int maxSP[] = new int[n]; int max = Integer.MIN_VALUE; // Construct the maxSP array for (int i = n - 1; i >= 0; i--) { if (prices[i] > max) { max = prices[i]; maxSP[i] = Integer.MIN_VALUE; } else { maxSP[i] = max; } } int profit = 0; for (int i = 0; i < n; i++) { if (maxSP[i] != Integer.MIN_VALUE) { profit = Math.max(profit, maxSP[i] - prices[i]); } } // Return profit return profit; } }
5
C++ Code for Best Time to Buy and Sell Stock problem
#include <bits/stdc++.h> using namespace std; int maxProfit(int *prices, int n) { int maxSP[n]; int max = INT_MIN; // Construct the maxSP array for (int i = n - 1; i >= 0; i--) { if (prices[i] > max) { max = prices[i]; maxSP[i] = INT_MIN; } else { maxSP[i] = max; } } int profit = 0; for (int i = 0; i < n; i++) { if (maxSP[i] != INT_MIN) { profit = std::max(profit, maxSP[i] - prices[i]); } } // Return profit return profit; } int main() { // Prices array int prices[] = {7, 1, 5, 3, 6, 4}; // Calculating the max profit int ans = maxProfit(prices, sizeof(prices) / sizeof(prices[0])); // Print the answer cout<<ans<<endl; return 0; }
5
Complexity Analysis
Time Complexity
O(n), as we have traversed over n elements of the array, during the precomputation and calculation of maximum profit. The time complexity is linear.
Space Complexity
O(n), because during the precomputation part we were storing the maximum selling price on a day after the current day. Since it is stored for all the elements in the array. The space complexity is also linear.
where n is the number of elements in the array.