Best Profit in Single Sale

Step by step thinking and solution for the challenge : Dev challenge 228

Question: You work as a hotshot day trader at Wall Street. Someone tipped you off and you got hold on the different rates at which a particular stock will sell at (highly illegal activity).
Since you don't want to arise suspicion, you decided that you'll get into a single trade and get as much profit as possible.
What's the max profit you can get?

Eg: Price = [7,1,5,3,6,4], output = 5, Buy on day 2 and sell on day 5. 6 - 1 = 5.

Some rules :
1> Once you buy a stock you can sell only on a later day, ie you can't buy stock on day 4 and sell it on day 1.
2> You can perform only one transaction, ie if you buy on day 1 and sell on day 2, you can't buy/sell on any later day.
3> You can perform one transaction per day, ie either you can buy on that day or sell on that day. You can't buy and sell on the same day.

With that out of our way. Let's solve this.

Brute Force: O(n^2)
Brute force approach would be to go over prices and compute all possible sale prices and find the maximum among them.

var maxSale = function(prices){
     int maxprofit = 0;
        for (let i = 0; i < prices.length - 1; i++) {
            for (let j = i + 1; j < prices.length; j++) {
                let profit = prices[j] - prices[i];
                if (profit > maxprofit)
                    maxprofit = profit;
            }
        }
        return maxprofit;
}

Now let's work on optimizing it.

Observations :
1> We want to find the maximum profit, maximum profit occurs when our buy at the least price and sell at the maximum price.

One pass : O(n)
Let's maintain a variable minPrice, which tracks the minimum stock price.
We'll go through prices if at a day, the stock price is less than the minPrice till that day, reset the minPrice. If stock price is not less then check if we can get maximum profit by selling stock on that day.

var maxProfit = function(prices){

        // initially set to minimum price
        let minprice = Number.MIN_VALUE;

        // set max profit to 0
        let maxprofit = 0;
        for (let i = 0; i < prices.length; i++) { 

            // if Current price is less than minprice found till now, 
            // set min price to current price. 
            if (prices[i] < minprice)
                minprice = prices[i];

            // else check if selling stock on ith day will give us maximum profit.
            else if (prices[i] - minprice > maxprofit)
                maxprofit = prices[i] - minprice;
        }
        return maxprofit;
}

Now you know how to earn profits by stock trading, go spend that hard earned money on your gold digger crush 🤪.

github : https://github.com/AKHILP96/Data-Structures-and-Algorithms/blob/master/problems/BuyAndSellStocks.js