Best Time to Buy and Sell Stock

The Solution to LeetCode easy problem

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

I will share two approaches here to solve the above problem-one is the Brute Force Approach & the Optimized Approach.

Brute Force Approach

In this for every element traverse the rest part of the array and find the profit using prices[j]-prices[i]; and keep comparing to find the maximum profit.

Since for every element you will have to traverse the rest part of the array, the time complexity will be O(n*n), but the space complexity will remain as O(1).

PS: I have given the logic above, try to code it yourself.💻✔

Optimal Approach

In this approach, we will do a linear traversal, our approach would be to find the smallest element in the left half and find the largest element in the other half. Simultaneously I will keep comparing to find the maximum profit.

Now let us do a dry run of the solution to understand it better.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int min_price = INT_MAX; // or take it as 999 anything
        int max_Profit = 0;
        for(int i=0;i<prices.size();i++)
        {
            min_price = min(min_price,prices[i]);
            max_Profit = max(max_Profit,prices[i]-min_price);
        }
        return max_Profit;
    }
};
Dry Run : prices = [7,1,5,3,6,4]
min_price = INT_MAX
max_Profit = 0
min_price = min(INT_MAX,7) = 7
max_Profit = max(0,1-7) = max(0,-6) = 0
min_price = min(7,1) = 1
max_Profit = max(0,1-1) = max(0,0) = 0
min_price = min(1,5) = 1
max_Profit = max(0,5-1) = max(0,4) = 4
min_price = min(1,3) = 1
max_Profit = max(4,3-1) = max(4,2) = 4
min_price = min(1,6) = 1
max_Profit = max(4,6-1) = max(4,5) = 5
min_price = min(1,4) = 1
max_Profit = max(5,4-1) = max(5,3) = 5
So therefore the maximum profit would be 5. 
Day of buying stock is 2 i.e prices[1] = 1
Day of selling stock is 5 i.e prices[4] = 6
So maximum profit is = prices[4] - prices[1] = 6 - 1 = 5

Time Complexity — O(n)

Space Complexity -O(1)

I am sharing some useful resources below :

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

https://www.youtube.com/watch?v=eMSfBgbiEjk&list=PLgUwDviBIf0rPG3Ictpu74YWBQ1CaBkm2&index=12

Hope you have understood the approach above. In case of any queries feel free to comment below. Till then keep coding and keep learning, Remember consistency is the key!!!

Since you enjoyed reading my blog , why not buy me a coffee and supoort my work here!! https://www.buymeacoffee.com/sukanyabharati ☕

Don’t forget to follow The Lean Programmer Publication for more such articles, and subscribe to our newsletter tinyletter.com/TheLeanProgrammer