Best Time to Buy and Sell Stock – Revisited

It is once again Sunday. Time seems to keep passing on faster. I assume this has to do with the COVID-19 pandemic. Since most of us are limiting our social activities, the days and weeks seem to be much of a replay. The good news is that people are starting to get vaccinated and spring is just around the corner.

After chatting with a software development manager I decided to revisit LeetCode 121. Best Time to Buy and Sell Stock which is ranked as Easy by LeetCode.

A few months ago I generated a post named Best Time to Buy and Sell Stock – Java. The problem is the same one we are covering today. The reason for the rewrite is to emphasize on how a problem is presented in order to provide enough and clear information regarding the requirements.

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock 
and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. 
If you cannot achieve any profit, return 0.

Constraints:

o 1 <= prices.length <= 105
o 0 <= prices[i] <= 104

The requirements for the problem have been updated at the LeetCode site. If you compare the older and the current descriptions, the wording has changed. In addition there are two examples that help you understand what is required.

Like on the previous related post, I will solve the problem using Java on a Windows 10 computer using the VSCode IDE.

public int maxProfit(int[] prices) {
	
}

The signature of the method of interest has not changed.

7,1,5,3,6,4
main <<< prices: [7, 1, 5, 3, 6, 4]
maxProfit <<< i: 1 minPrice: 1 maxProfit: 0
maxProfit <<< i: 2 minPrice: 1 maxProfit: 4
maxProfit <<< i: 3 minPrice: 1 maxProfit: 4
maxProfit <<< i: 4 minPrice: 1 maxProfit: 5
maxProfit <<< i: 5 minPrice: 1 maxProfit: 5
main <<< profit: 5


7,6,4,3,1
main <<< prices: [7, 6, 4, 3, 1]
maxProfit <<< i: 1 minPrice: 6 maxProfit: 0
maxProfit <<< i: 2 minPrice: 4 maxProfit: 0
maxProfit <<< i: 3 minPrice: 3 maxProfit: 0
maxProfit <<< i: 4 minPrice: 1 maxProfit: 0
main <<< profit: 0


7,6,5,4,3,2,1
main <<< prices: [7, 6, 5, 4, 3, 2, 1]
maxProfit <<< i: 1 minPrice: 6 maxProfit: 0
maxProfit <<< i: 2 minPrice: 5 maxProfit: 0
maxProfit <<< i: 3 minPrice: 4 maxProfit: 0
maxProfit <<< i: 4 minPrice: 3 maxProfit: 0
maxProfit <<< i: 5 minPrice: 2 maxProfit: 0
maxProfit <<< i: 6 minPrice: 1 maxProfit: 0
main <<< profit: 0


1,2,3,4,5,6,7
main <<< prices: [1, 2, 3, 4, 5, 6, 7]
maxProfit <<< i: 1 minPrice: 1 maxProfit: 1
maxProfit <<< i: 2 minPrice: 1 maxProfit: 2
maxProfit <<< i: 3 minPrice: 1 maxProfit: 3
maxProfit <<< i: 4 minPrice: 1 maxProfit: 4
maxProfit <<< i: 5 minPrice: 1 maxProfit: 5
maxProfit <<< i: 6 minPrice: 1 maxProfit: 6
main <<< profit: 6

Our test scaffolding which is NOT PART OF THE SOLUTION, reads the line of data, generates and populates an int[] with the values and displays them.

Each value represents the price of certain stock for a specified number of days. In the first example we are given stock prices for six consecutive days. If we buy stock on the first day we will make no profit (we would have a $6 loss). If we would buy on the second day at a price of $1 and wait to sell it until the fifth day, we would maximize profits per stock to $5.

The requirements clearly specify that we need to buy on a day when the stock is lowest and sell when the stock is highest. We fully understand the requirements so the task is to figure out a way to proceed.

    /**
     * Test scaffolding
     * 
     * !!!! NOT PART OF THE SOLUTION !!!!
     * 
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read price data ****
        String[] strs = br.readLine().trim().split(",");

        // **** close buffered reader ****
        br.close();
        
        // **** create and populate array of prices ****
        int[] prices = Arrays.stream(strs)
                            .mapToInt(Integer::parseInt)
                            .toArray();

        // ???? ????
        System.out.println("main <<< prices: " + Arrays.toString(prices));

        // **** compute and display the max profit ****
        System.out.println("main <<< profit: " + maxProfit(prices));
    }

We have the code for our test code. This code is NOT PART OF THE SOLUTION. We just need something to collect the data, present it to the method of interest, execute the code in the method and then display the returned value. If you decide to solve the problem on-line at LeetCode, you can use the provided IDE and avoid having to write the test scaffolding.

    /**
     * Return the maximum profit you can achieve from this transaction.
     * If you cannot achieve any profit, return 0.
     * 
     * Track min price (when to buy).
     * Track max profit (when to sell).
     * 
     * Runtime: 1 ms, faster than 98.84% of Java online submissions.
     * Memory Usage: 51.7 MB, less than 53.59% of Java online submissions.
     * 
     * Execution: O(n)
     */
    static int maxProfit(int[] prices) {

        // **** perform sanity check(s) ****
        if (prices.length < 2)
            return 0;

        // **** initialization ****
        int maxProfit   = 0;
        int minPrice    = prices[0];

        // **** traverse the array of prices - O(n)****
        for (int i = 1; i < prices.length; i++) {

            // **** look for the min stock price (when to BUY) ****
            if (prices[i] < minPrice)
                minPrice = prices[i];

            // **** compute max profit (when to SELL) ****
            else if (prices[i] - minPrice > maxProfit)
                maxProfit = prices[i] - minPrice;

            // ???? ????
            System.out.println( "maxProfit <<< i: " + i + " minPrice: " + minPrice + 
                                " maxProfit: " + maxProfit);
        }

        // **** return max profit ****
        return maxProfit;
    }

We start by performing a sanity check. We need to do this because the minPrice variable is set to the first entry in the prices array and the loop starts by accessing the second element in it.

The whole concept is based in first buying and then selling. We do so by entering a loop in which we will check all values in the array.

We check if the current value in the prices array is lower than the minimum price we have. If so we BUY the stock and move on to the next element.

If the stock for the current day is not lower, then we consider SELLING and making a profit. To do so we check if the profit is larger than what we currently have encountered and stored in the maxProfit variable. If so we update the contents of the maxProfit variable and move on to the next day.

Note that I have left uncommented the statement that displays the day, minPrice and maxProfit after we have bought or sold stock on that day. As you can see in the screen capture for each of the test cases, the logic can easily be followed.

When we exit the loop we return the value of the maxProfit variable.

Do not memorize problems. It is much better to understand them well and clarify requirements. English is not a programming language which is open to many interpretations. With very good requirements we avoid time wasted to get to a working solution. I always like to write a short requirement document with a few pictures instead of having no documentation or on the other hand a very long document which is hard to read and maintain. Software engineering is both a science and an art.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.

One last thing, many thanks to all 6,741 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.

Regards;

John

john.canessa@gmail.com

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.