Leeetcode - Best time to buy and sell stock to get maximum profit

Question

Question

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

If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Note that you cannot sell a stock before you buy one.

Example 1:

Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) 
             and sell on day 5 (price = 6), profit = 6-1 = 5.
             Not 7-1 = 6, as selling price needs to be larger than 
             buying price.

Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

My Approach is brute force.(Naive approach) Take each element and iterate through right to see how much profit can be made.

public int maxProfit(int[] prices) {
        int size = prices.length;

        if(size == 0 || size == 1) {
            return 0;
        }

        int maxProfit = 0;
        // Iterate through each right element.
        for(int i =0; i<size; i++) {
            for(int j = i+1; j<size; j++) {
                if(prices[j] > prices[i]) {
                    int diff = prices[j] - prices[i];
                    if(diff > maxProfit) {
                        maxProfit = diff;
                    }
                }
            }
        }

        return maxProfit;
    }

How can I improve this from O(n2) . Also, what if more than 1 transactions are allowed to get the profit.

Answer 1

Your use of whitespace is inconsistent, which makes the code harder to read and understand. There should be whitespace between control flow statements and open parentheses, and there should be whitespace on both sides of operators.

Your comment is noise and should be deleted.

Unless leetcode promises you'll never get a null input, you should check to make sure the prices array is not null.

It's cleaner to check if the array length is < 2 rather than enumerating the cases. Also, your algorithm works correctly without the check, since the loop falls through correctly.

size should be marked as final since it does not change. There's also no real value in storing this in a variable, since it's obvious what prices.length is, and it's not a computed value.

You can use Math.max() instead of doing subtraction and int comparison yourself. It makes the code easier to read.

You can save a comparison in some cases by always doing the subtraction. It's easier to read, and in some cases will be faster.

If you were to make all these changes, your code might look more like:

public int maxProfit(final int[] prices) {
    if (prices == null) {
        return 0;
    }

    int maxProfit = 0;

    for (int i = 0; i < prices.length; i++) {
        for (int j = i + 1; j < prices.length; j++) {
            maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
        }
    }

    return maxProfit;
}

As far as algorithmic performance, you can do this in O(n) time and O(1) space. Walk through the input array one time, tracking the minimum value seen so far and the current best profit. At each step, update those two values.

public int maxProfit(final int[] prices) {
    if (prices == null) {
        return 0;
    }

    int minPrice = Integer.MAX_VALUE;
    int maxProfit = 0;

    for (int i = 0; i < prices.length; i++) {
        maxProfit = Math.max(maxProfit, prices[i] - minPrice);
        minPrice = Math.min(minPrice, prices[i]);
    }

    return maxProfit;
}

Answer 2

I assume this assignment if for your own exercise, so giving you the source code of the solution is contraproductive. So I will only give you hints how to rewrite your code. Once done, post it here and we can compare it with my solution.

• You can avoid a whole inner loop cycle if you look ahead one item in your outer loop. In your example 1, your first loop would compare 7 with all others. Your second loop would compare 1 with all others. Since 1 < 7 you can skip comparing with all others in your first loop and only do the comparisons in your second loop. That means if it gets cheaper to buy every day, then skip until the day it becomes more expensive.
• You can avoid a whole inner loop cycle if you remember the old value from the outer loop and compare it to the current value. That means in your example, you compare buyPrice=1 and buyPrice=5. Because 1 < 5, you can skip the inner loop for 5 and just leave maxProfit as it is. In other words, the profit cannot become bigger if you buy it more expensive the next day(s) and sell it with the same price.
• Once you go through the inner loop, remember the maximum selling price and its position. The next time you go through the inner loop, you can reuse this maximum instead of iterating through all elements. (of course only if its position is still inside the new inner loop elements).
• Just delete the line "if(prices[j] > prices[i])". Subtracting two integers is as fast as comparing them in machine language.
• Follow DRY principle (clean code, red grade): instead of copy-pasting "prices[j]" just assign it to a variable with a meaningful name, for example "int buyPrice=prices[j]", in opposition to "int sellPrice=prices[i]".
• Guard your code: "prices.length" can throw a nullPointerException!
• "if(size == 0 || size == 1)" can be written faster and more clearly as "if(size <= 1)"

The maxProfit from your example 1 is 6 - 1 = 5. If more than 1 transaction is allowed, you could buy for 1 (second day) and sell for 5 (third day), then you could again buy for 3 (fourth day) and sell for 6 (fifth day). You overall profit would be 5-1 + 6-3 = 7. That's much more than if only 1 transaction is allowed.