Best time to buy and sell stock

Given an array arr of n integers, where arr[i] represents price of the stock on the ith day. Determine the maximum profit achievable by buying and selling the stock at most once.

The stock should be purchased before selling it, and both actions cannot occur on the same day.

Brute Force#

Try every pair (i, j) where i < j and compute the profit arr[j] - arr[i]. Track the maximum across all pairs. This is correct but requires O(n²) comparisons and results in a Time Limit Exceeded verdict for large inputs — we are re-examining many buy-sell pairs that cannot possibly yield a better answer.

class Solution{
public:
    int stockBuySell(vector<int> arr, int n){
        int maxProfit = INT_MIN;

        for(int i=0;i<arr.size();i++){
            for(int j=i+1;j<arr.size();j++){
                maxProfit = max(maxProfit, arr[j]-arr[i]);
            }
        }
        return maxProfit > 0 ? maxProfit : 0;
    }
};

Time Complexity: O(n^2) --> TLE

Space Complexity: O(1)

Optimal Approach#

Observe that to maximise profit on day i, we want the cheapest buy price seen on any day before i. A single left-to-right scan maintains a running cheapestStock and computes arr[i] - cheapestStock at each step, updating the max profit whenever we find a better gain. This collapses the nested loops into one pass, reducing time to O(n) while keeping O(1) space.

class Solution{
public:
    int stockBuySell(vector<int> arr, int n){
        int maxProfit = INT_MIN;

        int cheapestStock=arr[0];
        for(int i=1;i<arr.size();i++){
            if(arr[i] < cheapestStock)
                cheapestStock = arr[i];

            maxProfit = max(maxProfit, arr[i]-cheapestStock);
        }
        return maxProfit > 0 ? maxProfit : 0;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)