Best Time to Buy and Sell Stock – Leetcode #121

Problem Statement

This problem is from Leetcode – Best Time to Buy and Sell Stock. The problem statement is as below:

You are given an array prices where prices[i] is the price of a given stock on the i^th day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Solution

This problem is asking us to figure out that as we are moving forward in the prices array, which is the best day to to purchase stock and which is the best day to sell it, keeping in mind that profit should be maximum.

Approach-1

Lets see the brute force approach first:

1. Initialize maxProfit variable to zero.
2. Iterate the prices array till second last value, and at every index compute – what is max price in the remaining array ? This task can be delegated to another helper function getMax () which returns the desired value. Store this in a variable – maxValAtIndex.
3. Now compute profit at this index by subtracting price at this index from maxValAtIndex. Store this value in a variable curProfit.
4. Now compare curProfit with maxProfit and if curProfit is greater then store its value in maxProfit . So at every index we are computing the max profit value.
5. When iteration is over, then return the maxProfit value.

Lets see the code sample below:

      /*
	  * Function to find max profit from input stock prices.
	  * Input array -> int[] prices = {7,1,5,3,6,4};
	  */
	 public int maxProfit(int[] prices) {
		 
		 int maxProfit = 0;
		 int curProfit = 0;
		 int maxValAtIndex = -1;
		 
		
		/*
		 * Iterate the prices array in a for loop and find 
		 *  max price at every index
		 */
		 for(int i=0; i<prices.length-1; i++) {
			 
			 maxValAtIndex = getMax(i, prices);
			 
			 // compute profit at this index
			 curProfit = maxValAtIndex - prices[i];
			 
			 // if profit at this index is higher than current max profit, then store it as max profit
			 maxProfit = Math.max(maxProfit, curProfit);
		 }		 
		 
		 return maxProfit;
	 }
	 
	 /*
	  * compute the max value starting from the 
	  *  given index only
	  */
	 int getMax(int index, int[] prices) {
		 
		 // create a new ArrayList
		 List<Integer> pricesList = new ArrayList<>();
		 int max = 0;
		 
		 /*
		  * Iterate the prices array from the given 
		  *  index and populate the ArrayList
		  */
		 for(int i=index+1; i<prices.length; i++) {
			 
			 pricesList.add(prices[i]);
		 }
		 
		 // compute the max val in this list
		 max = (int) Collections.max(pricesList); 
		 
		 return max;
	 }

This code return the following output:

Max Profit: 5

You can check out the code from Github here: Best Time to Buy and Sell Stock – First Approach

Approach-2

Lets now try to solve this problem in one pass only and achieve time complexity of O(n).

1. Initialize maxProfit variable to zero.
2. Initialize the buy day / index to zero. This stores the array index when the stock price is lowest so far in the array.
3. Iterate the prices array from first index till last index. Now as we are moving forward we need to compute the best day / index to sell. This day is when the price difference is highest ( between current price and lowest price so far in the array ).
4. Maintain lowest price so far in the array in a variable min. This has the minimum stock price from array index zero till array index sell.
5. We are also interested in array index when prices are lowest so far in the array. Save this array index in the above variable buy.
6. At every index compute the current Profit by computing prices[sell] – prices[buy].
7. If the current profit is higher then the max profit then store its value in maxProfit.
8. When the iteration is over then return maxProfit as answer.

Lets see the code sample below:

 /*
	  * Function to find max profit from input stock prices.
	  * Input array -> int[] prices = {7,1,5,3,6,4};
	  */
	public int maxProfit(int[] prices) {
		
		// Initialize max profit to zero
		int maxProfit = 0;
		
		int curProfit = 0;
		int min = 0;
		
		// initialize the buy index to zero 
		int buy = 0;
		
		/*
		 * Iterate the prices array in a for loop starting first index
		 * 
		 */
		 for(int sell=1; sell<prices.length; sell++) {
			 
			 // store the lowest price so far in min
			 min = prices[buy];
			 	 
			 // if a lower price is encountered then
			 if(min > prices[sell]) {
				 
				 // 1. update min
				 min = prices[sell];
				 
				 // 2. update buy index to indicate the min price so far in array
				 buy = sell;
			 }
			 
			 // at every index compute the current profit
			 curProfit = prices[sell] - prices[buy];
			 
			 
			 /*
			  * if current profit is greater than max profit, then 
			  * store its value in max profit
			  */
			 
			 maxProfit = Math.max(maxProfit, curProfit);
		 }
		
		
		return maxProfit;
	}

This code returns the output as below:

Max Profit: 5

You can check out the code from Github here: Best Time to Buy and Sell Stock – Second Approach