121. Best Time to Buy and Sell Stock

Problem description

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 <= 105

0 <= prices[i] <= 104

Intuition:

The key idea behind this solution is to keep track of the minimum price seen so far (mini) and the maximum profit that can be achieved by selling the stock on a given day (maxi - mini). By iterating through the prices array, the algorithm updates these variables accordingly to find the maximum profit.

Approach:

Initialize mini and maxi variables to the first element of the prices array.

Iterate through each element i in the prices array:

Update mini if the current price is less than mini.

Update maxi if the current price is greater than maxi.

Update ret (maximum profit) by taking the maximum of ret and the difference between maxi and mini.

Return the final value of ret.

Complexity Analysis:

Time Complexity: The algorithm iterates through the prices array once, so the time complexity is O(n), where n is the length of the prices array.

Space Complexity: The algorithm uses a constant amount of extra space for variables mini, maxi, and ret, regardless of the size of the input array. Thus, the space complexity is O(1).

Summary:

This solution efficiently finds the maximum profit that can be achieved by buying and selling stocks, using a simple approach that only requires a single pass through the array. It achieves a time complexity of O(n) and a space complexity of O(1), making it an optimal solution for the given problem.

Code


public class Solution {
    public int MaxProfit(int[] prices) {
        int mini = prices[0];
        int maxi = prices[0];
        int ret = 0;
        foreach(int i in prices) {
            if(i < mini) {
                mini = i;
                maxi = i;
            }
            if(i>maxi) {
                maxi = i;
            }
            ret = Math.Max(ret, maxi-mini);
        }
        return ret;
    }
}