Striver's SDE Sheet Journey - #6 Stock Buy And Sell

Problem Statement :-

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.

Solution 1

by using 2 loops we can easily solve this problem. 1st loop buys the stock, the second loop sells the stock. by each selling, we maintain the max profit.

lets understand this step by step,

step-1 initialize a variable maxProfit=0.

step-2 run a loop from i=0 to prices.length.

1. initialize buyPrice = prices[i]
2. run another loop from j=i+1 to prices.length.

1. initialize sellPrice = prices[j]
2. if sellPrice > buyPrice then,

1.calculate the profit.
profit = sellPrice - buyPrice
2. if profit > maxProfit then,update the maxProfit.
maxProfit = profit

step-3 end.

have a at look this pic for a better understanding.

Java

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;

        for(int i=0; i<prices.length;i++){
            int buyPrice = prices[i];

            for(int j=i+1;j<prices.length;j++){
                int sellPrice = prices[j];

                if(sellPrice > buyPrice){

                    int profit = sellPrice - buyPrice;

                    if(profit > maxProfit)
                        maxProfit = profit;
                }
            }
        }

        return maxProfit;
    }
}

Time Complexity⏱️

we are running two loops then,
Time Complexity: O(n*n)

Space Complexity⛰️

we are not using any extra space then,
Space Complexity: O(1)

Solution 2

this problem can be solve by using kadane's algorithm with O(n) Time Complexity.

step-1 initialize three variables
buyPrice = prices[0],
sellPrice,
maxProfit = 0,

step-2 run a loop from i=1 to prices.length and then,

1. initialize sellPrice = prices[i]
2. if sellPrice < buyPrice then update the buyPrice,
buyPrice = sellPrice.
3. calculate the profit.
profit = sellPrice - buyPrice

4. if profit > maxProfit then update the maxProfit
maxProfit = profit

step-3 end.

class Solution {
    public int maxProfit(int[] prices) {

        int buyPrice = prices[0];
        int sellPrice;
        int maxProfit = 0;

        for(int i = 1; i<prices.length; i++){

            sellPrice = prices[i];

            if(sellPrice < buyPrice)
                buyPrice = sellPrice;

            int profit = sellPrice - buyPrice;

            if(maxProfit < profit)
                maxProfit = profit;


        }


        return maxProfit;
    }
}

thank you for reading this article. if you find any mistake let me know in the comment section.