Skip to content

122. Best Time to Buy and Sell Stock II

Given an integer array prices , prices[i] is the price of a given stock on the ith day. If can hold only a single share and can buy and/or sell the stock on same day.

Find the maximum profit possible.

Intuition

  • To achieve the max profit we need to buy on low day and sell on high day.
  • Since we can buy/sell multiple times we perform trades where \(price\[i] < price\[i+1]\)
  • If \(price\[i-1] < price\[i] < price\[i+1]\) we hold on day \(i\) as we can sell on day \(i+1\).

Approach

  • Iterate over the array while maintaining buy price.
  • If we encounter day where price next day will be higher we hold
  • If the price the next day is less, sell now and buy tomorrow

Complexity

  • Time complexity : \(\text{O}(1)\)
  • we iterate over the array only once
  • Space complexity : \(\text{O}(1)\)
  • no extra space is needed

Code

public int maxProfit(int[] prices) {
    int maxProfit= 0, buyPrice = -1;


    for (int i = 0; i < prices.length -1; i++ ) {
        if(prices[i] <= prices[i+1]) {
            // hold if bought earlier
            // if we haven't baought earlier buy now
            if(buyPrice == -1) buyPrice = prices[i];
        } else {
            if(buyPrice != -1) {
                maxProfit += prices[i] - buyPrice;

                // to check if we can buy on same day for profit
                buyPrice = -1;
                i--;    
            }   
        }
    }

    // we bought at some point but couldn't sell
    // as everyday price increased so sell on the last day

    if(buyPrice != -1) {
        maxProfit += prices[prices.length-1] - buyPrice;
    }

    return maxProfit;
}

Comments