Best time to buy and sell stock II

Introduction

All of us study hard for placements, solve numerous questions related to DSA, study Computer Science Fundamentals, and learn how to design a scalable system. The ultimate goal is to crack our dream job. 

One important question commonly asked in interviews is, “Best time to buy and sell stock”. 

This blog will discuss the Best time to buy and sell stock problems, wherein the prices of the stocks will be stored in an array. You need to find the maximum profit possible. 

There are mainly three variations to this problem, the first one is where you can buy and sell a single stock, the second one is when you can buy and sell as many stocks as you want and the third one is where you can buy at most K Stocks. Here we are going to solve the problem where we can buy and sell as many stocks as we want i.e. the second type.

Recommended: It is recommended to solve this problem on your own before moving on.

Problem Statement 

The problem statement on hand says, “You are given integer array prices where prices[i] is the price of a given stock on an ith day. On each day, you may decide to buy and sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day. Find and return the maximum profit you can achieve"

In an interview, it is recommended first to analyze the problem statement properly. The question says, there is an integer array prices[] where prices[i] is the price of a given stock on an ith day, you need to find out the maximum profit possible with the following conditions.

  • On each day you may either buy or sell a stock.
  • At most one stock can be held at any time.
  • Purchasing and selling stock on the same day is possible.

Let us look at some examples:

Example 1:

Input: {7, 1, 5, 3, 6, 4}

Output: 7

Explanation:

Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.

Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Total profit is 4 + 3 = 7.

Example 2:

Input: 

{2, 4, 7, 1, 3, 5}

Output:

9

Explanation:

Buy on day 1(price = 2) and sell on day 3(price = 7), profit =7-2 = 5

Buy on day 4(price = 1) and sell on day 6(price = 5), profit = 5-1 = 4

Total profit is 5 + 4 = 9.

Approach 1: Brute Force 

Always start with the brute force strategy in an interview and then come up with an optimal solution. The brute force strategy for this problem is to find the maximum possible profit we can make by doing any number of transactions starting from the first day or the start index. Recursion will be used in this approach.

In this approach, we will be using recursion, where we will have a recursive method, maxProfitUtil (int prices[], int start), to find the maximum profit that we can make by doing any number of transactions starting from the start index.

To calculate this, we will iterate on our stock prices array starting from prices[start] till the last price. We will let the current price as the start of a transaction(buy price), and for each start, we will iterate over the next remaining prices and consider them as the end of the transaction(sell price). Let's say the sell index ends. So the profit for this transaction is profit is equal to prices[end] - prices[start]. Let it be equal to CR PROFIT (remember we will only choose that END index having price greater than the price of the START index. ). 

Now we will calculate the maximum profit possible for the days after the ending day of the current transaction using recursion. So the profit = profit + maxProfitUtil(prices, end + 1) and we will find the maximum of all possible profits.

Algorithm

The algorithm for the above approach is:

  • If there are no prices left to consider, return.
  • Initialize MAX with zero.
  • For all the prices i.e. from start to size - 1 index, where size denotes the size of the array. Purchase the stock at price[start].
    • Initialize the MaxProfit = 0
    • For remaining prices, j from i + 1 to size - 1, sell the stock, iff price[j] > price[i]/
      • currProfit = price[j] + price[i]
      • Calculate the maximum profit for the remaining prices and add to profit, profit = profit + maxProfit(prices, j + 1)
      • If profit > MaxProfit, MaxProfit = profit.

                  ○ If MaxProfit > MAX, MAX = MaxProfit.

  • Return MAX.

Implementation

The implementation of the algorithm in Java is given below:

public class Solution {

    public static int maxProfitUtil(int prices[], int start) {

        // If there are no prices left to consider, return

        if (start >= prices.length) {

            return 0;

        }

        // Initialize max with 0

        int max = 0;

        // For all prices i.e i from START to the SIZE - 1

        // index, where size denotes the size of the prices

        // array. Buy the stock(start transaction).

        for (int i = start; i < prices.length; i++) {

            // Initialize maxprofit with zero

            int maxprofit = 0;

            // For remianing prices, j from i + 1 to size - 1, sell the stock

            // if price[j] > price[i]

            for (int j = i + 1; j < prices.length; j++) {

                if (prices[i] < prices[j]) {

                    int profit = maxProfitUtil(prices, j + 1) + prices[j] - prices[i];

                    if (profit > maxprofit) {

                        maxprofit = profit;

                    }

                }

            }

            if (maxprofit > max) {

                max = maxprofit;

            }

        }

        // Finally returning the maximum profit

        return max;

    }

    public static int maxProfit(int[] prices) {

        return maxProfitUtil(prices, 0);

    }

    public static void main(String[] args) {

        int[] prices1 = {247135};

        System.out.println("The maximum profit possible from prices1[] is " +maxProfit(prices1));

        int[] prices2 = {5134245};

        System.out.println("The maximum profit possible from prices2[] is " +maxProfit(prices2));

    }

}

The output of the above program is:

The maximum profit possible from prices1[] is 9

The maximum profit possible from prices2[] is 76

Complexity Analysis

The time complexity of the above approach is O(N^N) where N is the size of the array

In the worst case, the recursive function is called N^N times for every element in the array, making the time complexity O(N^N).

The space complexity is O(N) considering the depth of the recursive stack.

Approach 2: Memoization

The time complexity of the above recursive approach is way too high. The interviewer in the next step will ask you to optimize it.

A possible optimization approach is to reduce the number of times we are calculating the profit starting from the start index. If we have already calculated the results starting from the start index, then we won’t calculate it again. This is called Memoization, a technique where partial results are recorded and then can be reused again without having to compute them again.

In this approach, we will be using recursion, where we will have a recursive method, let's say MaxProfitUtil(prices, start) to find the maximum profit that we can make by doing any number of transactions starting from the start index. 

First, we will check whether we have already calculated the results starting from the start index. If calculated, then we will return the results and won’t calculate them again. Otherwise, to calculate this we will iterate on our prices starting from prices[start] till the last price. We will set the current price as the start of a transaction(buy price) and for each start, we will iterate over the next remaining prices and consider them as the end of the transaction(sell price). Let’s say the sell index ends. So the profit for this transaction is profit is prices[end] - prices[start]. Let it be equal to CURPROFIT (remember we will only choose that END index having a price greater than the price of the START index.). Now we will calculate the maximum profit possible for the days after the ending day of the current transaction using recursion. So the profit = CURPROFIT + MaxProfitUtil(Prices, end+ 1), and we will find the maximum of all possible profits and store these results to be used in the future.

Algorithm

  1. If there are no prices left to consider, Return.
  2. If the result for START is already calculated, Return DP[START]. 
  3. Initialize MAX with zero.
  4. For all PRICES i.e  from START to the SIZE - 1 index, where size denotes the size of the prices array. Buy the stock(start transaction). 
  5. Initialize MAXPROFIT with zero.
  6. For remaining prices, j from i + 1 to SIZE - 1, Sell the stock(end transaction) if PRICE[j] > PRICE[i], 
    1. CURPROFIT = PRICE[j] - PRICE[i]. 
    2. Calculate the maximum profit for the remaining prices and add to profit, PROFIT += MAX_PROFIT(PRICES, j + 1). 
    3. If PROFIT > MAXPROFIT , MAXPROFIT = PROFIT.
  7.  If MAXPROFIT > MAX, MAX = MAXPROFIT.
  8.  Store the results in DP array, DP[START] = MAX, return MAX.

Implementation

import java.util.Arrays;

public class Solution {

    public static int maxProfitUtil(int[] prices, int start, int[] dp) {

        if (start >= prices.length) {

            return 0;

        }

        // If the result for start is already calculated

        // return dp[start]

        if (dp[start] != -1) {

            return dp[start];

        }

        // Initialize max with zero

        int max = 0;

        // for all prices i.e. from start to size - 1, purchase the stock.

        for (int i = start; i < prices.length; i++) {

            // Initialize maxprofit with zero.

            int maxprofit = 0;

            // For remaining prices, j from i + 1 to size, sell the stock

            for (int j = i + 1; j < prices.length; j++) {

                if (prices[i] < prices[j]) {

                    int profit = maxProfitUtil(prices, j + 1, dp) + prices[j] - prices[i];

 

                    if (profit > maxprofit) {

                        maxprofit = profit;

                    }

              }

            }

            if (maxprofit > max) {

                max = maxprofit;

            }

        }

        // Store the result in dp array

        dp[start] = max;

        // return max

        return max;

    }

    public static int maxProfit(int[] prices) {

        int dp[] = new int[prices.length];

        Arrays.fill(dp, -1);

        return maxProfitUtil(prices, 0, dp);

    }

   public static void main(String[] args) {

        int[] prices1 = {247135};

        System.out.println("The maximum profit possible from prices1[] is " +maxProfit(prices1));

 

        int[] prices2 = {5134245};

        System.out.println("The maximum profit possible from prices2[] is " +maxProfit(prices2));

    }

}

 

The output of the above program is:

The maximum profit possible from prices1[] is 9

The maximum profit possible from prices2[] is 76

Complexity Analysis

The time complexity is O(N^2) where N is the number of days for which prices are given.

The space complexity is O(N), as in the worst case we will be memoizing results for N days.

Approach 3: Peak Valley 

Approach 2 is better than Approach 1 in terms of time complexity. But there is still scope for optimization. Let us try to analyze the input and output carefully

prices = {2, 4, 7, 1, 3, 5}

Let’s plot the stock prices on a graph, and try to visualize a pattern.

It can be easily observed that buying the stock on troughs and selling on the first peaks will give the maximum profit.

Transaction 1: Buy on first trough at price = 2

Sell on first peak at price = 7

Profit = 7 - 2 = 5

Transaction 2: Buy at second trough at price = 1

Sell on second peak at price = 5

Profit = 5 - 1 = 4

Total profit = 5 + 4 = 9.

The key point is we need to consider every peak immediately following a valley to maximize the profit. In case we skip one of the peaks (trying to obtain more profit), we will end up losing the profit over one of the transactions leading to an overall lesser profit.

Algorithm

  1. Initialize maxProfit = 0. Initially consider the first stock value as both the peak and valley for a new transaction.
  2. Linearly iterate over the prices[] array starting from day 2 or index = 1 to the end of the array.  
  3. Check if the current stock price is greater than the previous stock price. If it is true, then the current stock price will be the peak. 
    1. If the last price is the peak stock price, then maxProfit = maxProfit + (peak - valley).

      4. If the current stock price is not greater than the previous, then maxProfit = maxProfit + (peak - valley). The new transaction should start from the ith day. The valley will be prices[i]    and the new peak will be the valley.

      5.    Return the maxProfit.

Implementation

The implementation of the above approach is:

public class Solution {

    public static int maxProfit(int[] prices) {

        int maxprofit = 0;

 // To store the valley i.e the lowest price for a new transaction.

        int valley = prices[0];

// To store the peak i.e the maximum price for a new transaction.

        int peak = prices[0];

        for (int i = 1; i < prices.length; i++) {

// If the current price is not less than previous price, it will be the new peak

            // for current transaction.

            if (prices[i] >= prices[i - 1]) {

                peak = prices[i];

                // If the last price is a peak value.

                if (i == prices.length - 1) {

                    maxprofit += peak - valley;

                }

            } else {

                // We found a new valley, so we will end our current transaction completes.

                maxprofit += peak - valley;

                // New transaction should start from ith day.

                valley = prices[i];

                peak = valley;

            }

        }

        return maxprofit;

    }

    public static void main(String[] args) {

        int[] prices = { 715364 };

        System.out.println("Maximum profit from prices array is " + maxProfit(prices));

 

        int[] prices1 = { 76431 };

        System.out.println("Maximum profit from prices array is " + maxProfit(prices1));

    }

}

 

 

The output of the above program is:

Maximum profit from prices array is 7

Maximum profit from prices array is 0

Complexity Analysis

The time complexity of the above program is O(N) as in the worst case we will be iterating over the input array once.

The space complexity is O(1) as no extra space is required.

Approach 4: Positive Slopes Contribution 

So far so good. We have successfully optimized the brute force approach from O(N^N) time complexity to O(N) time complexity. The concept of peaks and valleys discussed above can be further modified to obtain the solution in a much more efficient way.

Lets carefully the graph for stock prices[] = {2, 4, 7, 1, 3, 5}

We know that profit = 9 in this case.

If you observe carefully you will notice that the profit is simply equal to the difference of all the consecutive price pairs wherein each pair the prices on an ith day is greater than the price on (i-1)th day.

In the above example,  (2, 4) will form such a pair as 4 > 2. Profit = 2

(7, 4) is also a possible pair. Profit = 3

(1, 3) is also a possible pair, Profit = 2

(3, 5) is also a possible pair, Profit = 2

Total profit = 9.

You must try other examples in the same way we discussed above on your own to understand the intuition behind them. 

Algorithm

  1. Initialize maxProfit equal to 0.
  2. Linearly iterate over the array. If the current price is greater than the previous price, or a positive slope is formed between the previous price and the current price. Then the current price - the previous price will be added to the maximum profit.
  3. Return the maximum profit.

Implementation

The implementation of the above algorithm is:

public class Solution {

    public static int maxProfit(int[] prices) {

        // Initialize maxprofit equal to 0

        int maxprofit = 0;

        // Linearly iterate over the array

        for (int i = 1; i < prices.length; i++) {

            // If the current price is greater than previous price, it should be added to the maxprofit.

            if (prices[i] >= prices[i - 1]) {

                maxprofit += prices[i] - prices[i - 1];

            }

        }

        return maxprofit;

    }

    public static void main(String[] args) {

        int[] prices1 = {7152456};

        int[] prices2 = {76764134};

        System.out.println("Maximum profit in prices1 is " + maxProfit(prices1));

        System.out.println("Maximum profit in prices1 is " + maxProfit(prices2));

    }

}

 

 

The output of the above program is

Maximum profit in prices1 is 8

Maximum profit in prices1 is 103

Complexity Analysis

The time complexity of the above approach is O(N).

The space complexity is O(1).

Key Takeaways

The blog discussed an important interview problem, the best time to buy and sell stock. Various approaches along with code in java were discussed. With this done, you may practice more questions related to Arrays.

A common problem faced by all of us is we prepare well, but during online assessments, we are unable to solve the questions on time. To overcome this, Coding Ninjas have come up with an online mock test series. The mock tests for leading companies like Amazon, Microsoft, Google, Adobe, Flipkart, TCS, Wipro, and Accenture are available for free. Our team of experts has curated and designed these online mock test series to help you prepare better for your coding interview rounds. In this online test series, you will get multiple tests that include the latest coding interview questions. Start preparing for the 2021 Amazon, Microsoft, etc., tech interviews now.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think