LeetCode Solution: Best Time to Buy and Sell Stock Problem

Hello Everyone!

Hope you are making the best out of this Quarantine period to improve your coding and problem-solving skills.

As you might be getting to hear a lot about the stock market hitting its lowest point ever in recent years due to the lockdown situation, here we have come up with a logic behind the Best Time to Buy and Sell Stocks (as per the problem statement that very much relates to the actual stock market logic), to help you learn the concept behind making the investment decisions.

In this post, we are going to discuss the solution and the logic behind the Best Time to Buy and Sell Stock II problem of the 30 Days coding challenge on LeetCode.

So let's get started without any further delay.

LeetCode Solution: Best Time to Buy and Sell Stock Problem

Problem Statement:

Say you have an array prices for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

NOTE: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7

Explanation:

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

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

This way, the net profit = 4 + 3 = 7, which is the required output.

Let's consider another example to develop a better understanding of the problem statement:

Example 2:

Input: [1,2,3,4,5]
Output: 4

Explanation:

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

2. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging in multiple transactions at the same time. You must sell before buying again.

Let's consider one more example that would cover one of the special cases that we need to handle while providing the solution.

Example 3:

Input: [7,6,4,3,1]
Output: 0

Explanation: In this case, no transaction is done, i.e. max profit = 0. (as the array is sorted in decreasing order and hence, any number in the future will always be lesser than the current one resulting in a loss)

Best Time to Buy and Sell Stocks Program Solution

On looking closely at all three examples mentioned above, one can develop the intuition that the solution to this problem is quite simple.

• Constraints:

  • There is a restriction that we have to first purchase the stock and sell it in the upcoming days (not the current day).

  • We can purchase another stock only once the previously purchased stock is sold.

  • The stock exchange will only be added to the profit if we first purchase it at a lower price and then sell it at a higher price.

• The fundamental logic behind making a profit in the stock exchange is purchasing the stock at a relatively lower price and selling at a higher price.

• As a result, if the difference between the current and the next number results in a positive value, that will be added to the profit.

• If it results in a negative value, that means it is not advisable to purchase it at the current price as it's getting lowered in the future.

• This way, we can store the difference between every two consecutive elements of the original array and can add all the positive values of this new array (that stores the differences) to calculate the net profit (variable s in the below code).

If you are still not clear with this logic, just try to implement it over any of the three examples mentioned above, and you will definitely get it.

Also, to help you understand the code as per the above logic, we have commented on the major portions of the solution, so that you can relate it to the stepwise logic provided above.

Code Solution: (written in Java)

class Solution {
    public int maxProfit(int[] p) {
        
        int n = p.length;
        
        /* The new array q will contain the difference between 
           each pair of the consecutive elements of the original 
           array and hence it's size would be 1 lesser than that 
           of the original array.
        */
        int[]  q = new int[n-1];
        
        int i=0,s=0;
        
        /* Updating each element of the new array to the difference 
           between the corresponding two elements of the original array.
        */
        while(i!=n-1)
        {
            q[i] = p[i+1]-p[i];
            i++;
        }
        int j=0;
        
        /* The final sum (profit) would be equal to the sum of all 
           the positive numbers in the new array q, as a positive 
           value denotes that the stock has been purchased on a lower 
           price and sold on a higher price, adding on to the net profit.
        */
        while(j != n-1)
        {
            if(q[j]>0)
            {
                s+=q[j];
            }
            j++;
        }
        return s;
    }
}

Conclusion

We hope that this step-by-step explanation to handle each of the possible scenarios might have helped you to understand the entire solution to the mentioned problem.

In case of any query, you can reach out to us via Email or can directly post your queries in the comments section down below.

Happy Quarantine : )

Frequently Asked Questions(FAQs)

1. What is the "Best Time to Buy and Sell Stock" problem?

The "Best Time to Buy and Sell Stock" problem requires finding the maximum profit that can be obtained by buying and selling a stock from a given list of prices, where you can only make one transaction (buy once and sell once).

2. What is the efficient solution approach for this problem?

The efficient solution approach for the "Best Time to Buy and Sell Stock" problem is to iterate through the list of prices, keeping track of the minimum price seen so far, and updating the maximum profit accordingly. This approach has a time complexity of O(n), where n is the number of prices.

3. What are dynamic programming techniques, and how are they relevant to this problem?

Dynamic programming is a problem-solving technique that involves breaking down a complex problem into smaller overlapping subproblems. Although dynamic programming is not directly applicable to the "Best Time to Buy and Sell Stock" problem, it can be useful for solving related problems with more complex constraints.

4. How can I find the minimum and maximum prices efficiently?

To find the minimum and maximum prices efficiently, you can use variables to track the minimum and maximum prices seen so far while iterating through the list of prices. Update these variables as you encounter lower minimums or higher maximums.

5. How can I further improve my problem-solving skills?

Improving problem-solving skills requires regular practice and exposure to various coding challenges. Explore platforms like LeetCode, participate in coding competitions, and solve a diverse range of problems. Additionally, analyzing and understanding efficient solutions shared by the programming community can help you learn new techniques and approaches.

You may also like:

• LeetCode Solution - First Bad Version Problem

• LeetCode Solution: Maximum Subarray Problem

• LeetCode Solution - Jewels and Stones Problem

• LeetCode Solution: Move Zeroes Problem