Data Structures and Algorithms in Java – Arrays – Best time to buy and sell stock

Problem:

You are given an array of stock prices with each index of the array representing each day.

You need to buy stock one one day and sell it on another subsequent day.

What is the maximum profit you can earn?

Input:

An integer array of prices:

 prices = [7,1,5,2,6,9]

prices[i] denotes the price on the "i"th day

Output:

8 (9 – 1)

Buy on day 2 (prices[1]) and sell on day 6 (prices[5])

Constraints:

You can only sell the stock after buying it .

There will be a minimum of one element in the price array and maximum upto 1 lakh elements

Each stock price may vary from 0 rupees to 10000 rupees

Try out the solution here:

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Solution:

The brute force solution for the above problem is to iterate through each element in the array and for each element find the difference with each other subsequent elements .

The maximum difference gives the maximum profit:

class Solution {
    public int maxProfit(int[] prices) {
        
      
    
        
        int profit = 0;
        
                
        for(int i=1;i< prices.length ;i++){
            
           for(int j = i+1 ; j < prices.length ; j++){
               
               
               int currentProfit = prices[j] - prices[i];
               
               if(currentProfit > profit){
                   
                   profit = currentProfit;
               }
           }
         
        }
        
        return profit;
        
    
}
        
    
}

This requires two for loops and the time complexity is O(n² )

The optimal solution can be done in O(n) time complexity.

Hint:

To find out the optimum solution you need to use the below hint:

• Keep track of the minimum price as you traverse the list of prices

Here is the solution using the above hint:

Algorithm:

STEP1: Assign the first price as the minimum price (buy price)

STEP2: Iterate through all other prices

STEP3: For each price calculate the profit by finding the difference with the minimum price

STEP4: If the calculated profit is greater than the previous profit , make it the maximum profit

STEP5: If current price is less than the minimum price , make the current price the minimum price (make sure you don’t do this comparison for the last element – if the last element is the smallest price you don’t have another day to sell it)

STEP6: Return the maximum profit

class Solution {
    public int maxProfit(int[] prices) {
        
      
    
        
        int profit = 0;
        
        int minPrice = prices[0];
        
        for(int i=1;i< prices.length ;i++){
            
        
                
            int currentProfit = prices[i] - minPrice;
            
            
            if(prices[i] > minPrice && currentProfit > profit){
                
                
                profit = currentProfit;
                
            }
            
            
            if(prices[i] < minPrice && i!=prices.length -1 ){
                
                
                minPrice= prices[i];
            }
            
            
        }
        
        return profit;
        
    
}
        
    
}

That’s it!

Reference:

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

https://www.geeksforgeeks.org/best-time-to-buy-and-sell-stock/