Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement 
3.
Peak Valley Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
Implementation
3.3.1.
Output
3.4.
Complexity Analysis
3.4.1.
Time Complexity
3.4.2.
Space Complexity
4.
Positive Slopes Approach
4.1.
Algorithm
4.2.
Dry Run
4.3.
Implementation
4.3.1.
Output
4.4.
Complexity Analysis
4.4.1.
Time Complexity
4.4.2.
Space Complexity
5.
Frequently Asked Questions
5.1.
What is recursion?
5.2.
What the problem “Best time to buy and sell stock ii” states?
5.3.
What is the peak valley approach?
5.4.
How is memoization helpful in solving problems?
5.5.
What is the time complexity to solve the problem?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Best time to buy and sell stock II

Author Ayushi Goyal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

We all 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". 

Introduction

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

Problem Statement 

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. It is recommended to solve this problem on your own before moving on.

problem statement

In an interview, it is recommended first to analyze the problem statement properly. The problem statement on hand says there is an integer array arr[] where arr[i] is a given stock's price 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 before discussing the approach of solving the problem:

Example 1:

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

Output: 9

Explanation:

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

Buy on day 4(arr[] = 1) and sell on day 6(arr[] = 5), profit = 5-1 = 4

Total profit is 5 + 4 = 9.
 

Example 2:

Input:  {7, 6, 5, 2, 4}

Output: 2

Explanation:

Buy on day 4(arr[] = 2) and sell on day 5(arr[] = 4), profit =4-2 = 2

There is no other combination possible because all other values are in descending order.
 

Example 3:

Input:  {5, 8, 1, 6, 3}

Output: 8

Explanation:

Buy on day 1(arr[] = 5) and sell on day 2(arr[] = 8), profit =8-5 = 3

Buy on day 3(arr[] = 1) and sell on day 4(arr[] = 6), profit =6-1 = 5

Total profit is 3 + 5 = 8. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Peak Valley Approach

The brute force approach exceeds the time limit, so let's optimize it using the peak valley approach. In this approach, we consider every peak value that is immediately followed by a valley. Let us discuss the algorithm used in this approach. 

Algorithm

  • Initialize maxProfit = 0. Initially, consider the first stock value as both the peak and valley for a new transaction.
  • Linearly iterate over the arr[] array starting from day two or index = 1 to the end of the array.  
  • Check if the current stock price is greater than the previous stock price. If it is true, the current stock price will peak.
  • If the last price is the peak stock price, then maxProfit = maxProfit + (peak - valley).
  • 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 arr[i], and the new peak will be the valley.
  • Return the maxProfit.

Dry Run

Let us try to analyze the input and output carefully according to the algorithm

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

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

graph of stocks

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

1st transaction

 

2nd transaction

So, Total profit = profit in transaction 1 + profit in transaction 2 = 5 + 4 = 9.

Implementation

The implementation of the algorithm is given below:

public class Main {
	public static int maxProfit(int[] arr) {
    	int maxprofit = 0;
    	
    	// To store the valley i.e the lowest price for a new transaction.
    	int valley = arr[0];
    	
    	// To store the peak i.e the maximum price for a new transaction.
    	int peak = arr[0];
    	
    	for (int i = 1; i < arr.length; i++) {
    	    /* If the current price is not less than previous price, 
    	       it will be the new peak
        	       for current transaction.*/
        	    if (arr[i] >= arr[i - 1]) {
                   peak = arr[i];
            	
                   // If the last price is a peak value.
                   if (i == arr.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 = arr[i];
                peak = valley;
            }
        }
    	return maxprofit;
    }
    public static void main(String[] args) {
        int[] arr1 = {1, 3, 8, 2, 4};
        int[] arr2 = {25, 32, 81, 2, 95};
        int[] arr3 = {3, 95, 25, 36, 74, 98};
        System.out.println("The maximum profit possible from arr1[] is " +maxProfit(arr1));
        System.out.println("The maximum profit possible from arr2[] is " +maxProfit(arr2));
        System.out.println("The maximum profit possible from arr3[] is " +maxProfit(arr3));

    }
}

Output

The output of the above program is:

output

Complexity Analysis

Time Complexity

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

Space Complexity

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

Positive Slopes Approach

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 much more efficiently.

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.

Dry Run

Let's carefully see the graph for stock arr[] = {2, 4, 7, 1, 3, 5}

graph of stocks

From the graph, you can easily calculate the profit as 9 in this case.

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

In the above example, the possible pairs will be:

possible pairs

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

Implementation

The implementation of the algorithm is given below:

public class Main {
public static int maxProfit(int[] arr) {
     // Initialize maxprofit equal to 0
     int maxprofit = 0;
    
     // Linearly iterate over the array
     for (int i = 1; i < arr.length; i++) {
         /* If the current price is greater than 
           previous price, it should be added to 
           the maxprofit.*/
         if (arr[i] >= arr[i - 1]) {
                maxprofit += arr[i] - arr[i - 1];
            }
        }
     return maxprofit;
    }
    public static void main(String[] args) {
        int[] arr1 = {1, 3, 8, 2, 4};
        int[] arr2 = {25, 32, 81, 2, 95};
        int[] arr3 = {3, 95, 25, 36, 74, 98};
        System.out.println("The maximum profit possible from arr1[] is " +maxProfit(arr1));
        System.out.println("The maximum profit possible from arr2[] is " +maxProfit(arr2));
        System.out.println("The maximum profit possible from arr3[] is " +maxProfit(arr3));
    }
}

Output

The output of the above program is:

output

Complexity Analysis

Time Complexity

The time complexity using the above approach is O(N). This is because we have done only one iteration starting from 1 to N, where N = length of the given array. 

Space Complexity

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

Frequently Asked Questions

What is recursion?

Recursion is the better way of solving a problem. It divides the problem into smaller parts calling the recursive function repeatedly.

What the problem “Best time to buy and sell stock ii” states?

The best time to buy and sell stocks II problem states that you have to find the maximum profile earned when you are allowed to buy and sell as many stocks as you want. 

What is the peak valley approach?

In the peak valley approach, we consider every peak value that is immediately followed by a valley. 

How is memoization helpful in solving problems?

Memoization helps in recording the data, which is calculated onces so that we don't need to calculate it again and again. It helps in saving a lot of time and cost. 

What is the time complexity to solve the problem?

The time complexity to solve this problem using brute force is O(N*N) and optimize approach is O(N).

Conclusion

The blog discussed an important interview problem, the best time to buy and sell stock ii. Various approaches, along with code, were discussed. With this done, you may practice more questions related to Arrays.
You can refer to other such problems using below links:

Please refer to our guided paths on Coding Ninjas Studio to learn more about DSACompetitive ProgrammingJava Programming, and System Design, etc. Have a look at the interview experiences and interview bundle for placement preparations. And also, enroll in our courses and refer to the mock test and problems available.

If you think that this blog helped you, then share it with your friends!

All the best for your future endeavors, and Keep Coding.

Previous article
Wildcard Matching
Next article
Best Time to Buy and Sell Stock III
Live masterclass