Jb Tak Fodega Nhi 🎯 Tb Tk Chodega Nhi 📚 (MAANG)

DPL35 Best Time to Buy and Sell Stock I

Best time to buy and sell stock I, We are given an array Arr[] of length n. It represents the price of a stock on ‘n’ days. The following guidelines need to be followed:

We can buy and sell a stock only once.

We can buy and sell the stock on any day but to sell the stock, we need to first buy it on the same or any previous day.

We need to tell the maximum profit one can get by buying and selling this stock.

In Best Time to Buy and Sell Stock I: We Allow Just Only 1 Transactions

How To Solved this Problem
For every index of string S1, we have different options to match that index with string S2. Therefore, we can think in terms of string matching path as we have done already in previous questions. Again this Problem Based on the DP on String Matching

Either the characters match already.

Or, if there is a ‘?’, we can explicitly match a single character.

For a ‘*’, the following figure explains the scenario.

VVVV Important Note:

Dp on Stocks its Very Important to Understand the Concept of the Space Optimization.

Becouse Recruter expect from your side you must know the concept of the Space Optimization on DP on Stocks.

We can not Escape teh Space Optimization.

Intuition Behid this Problem

We need to find the maximum profit. In order to maximize the profit, we need to buy the stock at its lowest price and sell it when the price is highest. In the given example the lowest price(1) is on Day 1 and the highest price is (7) is on Day 0. But we need to buy the stock before selling it therefore we need to modify this approach.

We can try to sell the stock every day and try to find the maximum profit that can be generated by selling the stock on that day. At last, we can return the maximum of these individual maximum profits as our answer.

To find the individual maximum profit on a day ‘i’, we know the selling price, i.e the price of the stock on day i, we need to find the buying price. To maximize the profit on day ‘i’, the buying price should be the lowest price of the stock from day 0 to day i (see the graph above). This way we can keep track of the correct buying price for any day.

Approch

The algorithm approach can be stated as:

Initialize a variable ‘maxProfit’ to 0 and declare another variable ‘mini’ which we will use to keep track of the buying price (minimum price from day 0 to day i) for selling the stock.

Traverse the array from index 1 to n-1. We started at index 1 because buying and selling the stock on the 0th day will give us a profit of 0, which we have initialized our maxProfit as already.

In each iteration, try to find the curProfit. The selling price will be Arr[i] and ‘mini’ will give us the buying price. We calculate the curProfit. If it is more than the existing profit value (maxProfit), we update the maxProfit value.

Before going to the next iteration, we check if the current price (Arr[i]) is less than the mini value, and we assign it as the new mini value. In this way, we keep track of the buying price in a single iteration itself.

Always Remember if we shell the Stocks on the ith Day then you buy on the minimum price from [0 to i-1] day

VVVV Important Note:
This Problem already take the liner time to solved this probelm and Space complexcity is Also take the Constant, so its not possible to more Optimized this Solution that's why we Direct the Optimial Code.

But in the Upcomming Problems on DP on Stock we will used the Same Approches and Flow that we used on the Previous Patterns on DP

Recursion Approch

Memoization Approch

Tabulation Approch

Space Optimization Approch (Most Important)

SpaceOptmized Python Code

class Solution:
        
    def maxProfit(self, prices):
  
        maxProfit = 0
        minPrice = prices[0]
                
        for index in range(1,len(prices)):
            currentStockPrice = prices[index] - minPrice
            maxProfit = max(maxProfit,currentStockPrice)
            minPrice = min(minPrice,prices[index])
        
        print(minPrice)
        return maxProfit

ans = Solution()
prices = [7,1,5,3,6,4]
print(ans.maxProfit(prices))

Time & Space Complexity

Time Complexity: O(N)
Reason: We are performing a single iteration
Space Complexity: O(1)
Reason: No extra space is used. Just we used the Some Variables for the Storing the Some Dummy Data

Interview Docs File "All the Best" Team @DSAwithPrinceSingh

~ It's All About Consistency📈 Dedication🎯 HardWork💪 Happy Coding❤️ ~