Leeetcode - Best time to buy and sell stock to get maximum profit 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&lt;size; i++) {
            for(int j = i+1; j&lt;size; j++) {
                if(prices[j] &gt; prices[i]) {
                    int diff = prices[j] - prices[i];
                    if(diff &gt; 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.
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 &lt; 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 &lt; prices.length; i++) {
        for (int j = i + 1; j &lt; 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 &lt; prices.length; i++) {
        maxProfit = Math.max(maxProfit, prices[i] - minPrice);
        minPrice = Math.min(minPrice, prices[i]);
    }

    return maxProfit;
}