DAY 5 - Best Time to Buy and Sell Stock

Hello to anyone reading this. I am still relatively new to coding and this platform as well, so please feel free to drop any corrections/advice for me.
I am trying to do the 100 Day-Challenge of consistent coding and this is Day-5.The goal is simple. I will solve one or more than one leetcode/gfg problem a day and post what I learnt. I am confident that this will help me improve my concepts and help me be more consistent in my practice. Looking forward to a positive interaction with all of you.

DAY-5 Problem 1: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:

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.

Intuition

The problem is very and direct and easy. It requires us the maximize the profit. In problems like maximization and minimization, we often use dynamic programming.
The first approach that comes to our mind would be the simple approach is to check for every buying and selling day and result out the maximum we can find.
But even while writing that approach, we feel like we can do better. So let's take a look at the optimal approach for this as well.

Approach:

Brute Force Approach
In the brute force approach, we are going to use two pointers and traverse the array using two for loops. One for selecting the buying day and one for the selling day. We will take their difference as the maximization and move the selling pointer ahead until we can't.

Code:

int maxProfit(vector<int>& nums) {
        int maxPro = 0;
        for(int i = 0; i < nums.size()-1; i++)
        {
            for(int j = i+1; j < nums.size(); j++)
            {
                maxPro = max(maxPro,nums[j]-nums[i]);
            }
        }
    return maxPro;   
    }

Complexity Analysis

Time Complexity: O(n^2)
Space Complexity: O(1)

Although this is an approach, in a time constrained environment. It will most likely fail.
So we are going to have to come up with a better approach.

Optimal Approach
We are going to take an approach that allows us to solve the problem in one pass. Henceforth making the time complexity O(n) while only using constant space.

We will use two variables here. One to store the maximum profit obtained(here maxPro) and one to store the minimum buying value we can find. We will then traverse the array one time taking difference to find the maximum Profit.

Dry Run on Example:

• Create a variable maxPro and store 0 in it initially.
• Create a variable minPrice and store arr[0] in it initially.
• Run a loop traversing the array and updating the minPrice if it is smaller than the current minPrice.
• Subtract that from the current iterator index and take maximum b/w that and maxPro.

Code:

int maxProfit(vector<int>& prices) {
        int x = prices[0];
        int maxPro = 0;
        for(int i = 0; i < prices.size();i++)
        {
            x = min(x,prices[i]);
            maxPro = max(maxPro,prices[i]-x);

        }
        return maxPro;
    }

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)
where n is the size of array.

This is it. Please feel free to ask any questions in the comment section.