Best Time To Buy And Sell Stock

Chaitra Rai

·

Follow

2 min read

·

Sep 8, 2021

--

Listen

Share

Given an array of prices, one must find when they would buy and sell stocks so that they would get the maximum profit. A stock should be bought before being able to sell it (Question 1, Question 2, Question 3)

• Let's consider a brute force approach where we would use two loops to find the difference between the bought and sold stock for each of the given prices
• This approach would take O(n²) time complexity and would not be ideal for large inputs

public int maxProfit(int[] prices) {
        int diff=0;
        int max_profit=0;
        for(int i=0;i<prices.length;i++){
            for(int j=i+1;j<prices.length;j++){
                diff=prices[j]-prices[i];
                max_profit=Math.max(diff,max_profit);
            }
        }
        return max_profit;
    }

• The approach is to find a minimum stock price and find a stock after that which is greater than this stock to gain a profit.
• Let us take a temporary variable to store the minimum values and calculate the profit gained as we traverse through the array
• The time complexity of the algorithm is O(n)

public int maxProfit(int[] prices) {
    int least_stock=Integer.MAX_VALUE;
    int max_profit_total=0;
    int max_profit_now=0;
    for(int i=0;i<prices.length;i++){
        if(prices[i]<least_stock)
            least_stock=prices[i];
        max_profit_now=prices[i]-least_stock;
        max_profit_total=Math.max(max_profit_now, max_profit_total);
    }
    return max_profit_total;
}

• Another variant of stock questions to buy a stock infinite number of times can be solved by finding a buying day with least stock price and finding a seliing day with maximum stock price
• buy the stocks whenever there is a least stock in a increasing section and sell the stock in the peak of the increasing section

public int maxProfit(int[] prices) {
    int buy_day=0;
    int sell_day=0;
    int max_profit=0;
    for(int i=1; i<prices.length; i++){
        if(prices[i]>prices[i-1])
            sell_day++;
        else{
            max_profit+=prices[sell_day]-prices[buy_day];
            buy_day=sell_day=i;
        }
    }
    max_profit+=prices[sell_day]-prices[buy_day];
    return max_profit;
}

• This has a time compelxity of O(n) and O(1) space complexity
• To sell the stocks atmost twice we can keep 2 arrays one to traverse ahead and one to traverse backward
• we find the stock profit while we travel forward and we find the stock profit while we travel backward and store the values in temporory arrays
• this way we get the the stock profits when sold twice as the sum of values in these two temporary values

public int maxProfit(int[] prices) {
    int n=prices.length;
    int max_backward_profit=Integer.MIN_VALUE;
    int max_forward_profit=Integer.MIN_VALUE;
    int total_profit=0;
    int least_value=prices[0];
    int max_value=prices[n-1];
    int[] forward_array=new int[n];
    int[] backward_array=new int[n];
    for(int i=0;i<n;i++){
        if(prices[i]<least_value)
            least_value=prices[i];
        else if(max_forward_profit<prices[i]-least_value)
            max_forward_profit=prices[i]-least_value;
        forward_array[i]=max_forward_profit;
    }
    for(int i=n-1;i>=0;i--){
        if(prices[i]>max_value)
            max_value=prices[i];
        else if(max_backward_profit<max_value-prices[i])
            max_backward_profit=max_value-prices[i];
        backward_array[i]=max_backward_profit;
    }
    for(int i=0;i<n;i++){
        if(total_profit<forward_array[i]+backward_array[i]){
            int sum=forward_array[i]+backward_array[i];
            total_profit=Math.max(total_profit,sum);
        }
    }
    return total_profit;
}

• This takes O(n) time complexity and O(n) extra space