Best Time To Buy And Sell Stock: 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.

Example 1:

Input: prices = [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.
Note that buying on day 2 and selling on day 1 is
not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

Try this Problem on your own or check similar problems:

1. Maximum Subarray
2. Best Time to Buy and Sell Stock II
3. Best Time to Buy and Sell Stock III

Solution:

public int maxProfit(int[] prices) {
    int maxProfit = 0, minPrice = Integer.MAX_VALUE;

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

    return maxProfit;
}

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

Explanation:

First thing to note from the problem statement is that you must buy before you sell, so the brute-force would be comparing current price with all next prices and check for the difference while updating the maxProfit. This will bring us to O(n^2) time complexity. We can do better! Also note that sorting wouldn’t work here since we’re dependent on the initial order (order of days). The first thing to notice is that there is certain locality vs globality in the array. But what does that mean? It means that for certain days we only care about local minimum (minimum that happened on one of the days before today) and we don’t care if that local minimum is also global (note that there might be elements/prices after “today” that are smaller than our current minimum). So, to achieve maxProfit we can be greedy, we can track the local minimum (or global for subarray ending at specific day), and check if we can earn more if we sell at certain day (prices[i] - minPrice).