Best Time to Buy and Sell Stock LeetCode Solution

Table of Contents

Problem Statement

The Best Time to Buy and Sell Stock LeetCode Solution – “Best Time to Buy and Sell Stock” states that You are given an array of prices where prices[i] is the price of a given stock on an 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:

prices = [7,1,5,3,6,4]

Explanation:

You can Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.

It is important to note that buying on day 2 and selling on day 1 is not permitted because you must buy before selling.

prices = [7,6,4,3,1]

Explanation:

In this situation, no transactions occur, and the maximum profit = 0.

Brute Force Solution

Idea:

For every jth day, we will check if we sell on it, what will be the maximum profit if we buy before the jth day.

Code:

C++ Program of Best Time to Buy and Sell Stock:

#include <bits/stdc++.h>
using namespace std;
 
int maxProfit(vector<int> &prices)
{
   int n = prices.size();
   int answer = 0;
   for (int i = 0; i < n; i++)
   {
       for (int j = i + 1; j < n; j++)
       {
           answer = max(answer, prices[j] - prices[i]);
       }
   }
   return answer;
}
int main()
{
   vector<int> prices = {7, 1, 5, 3, 6, 4};
   cout << maxProfit(prices) << endl;
   return 0;
}

JAVA Program of Best Time to Buy and Sell Stock:

public class TutorialCup
{
   public static int maxProfit(int[] prices)
   {
       int n = prices.length;
       int answer = 0;
       for (int i = 0; i < n; i++)
       {
           for (int j = i + 1; j < n; j++)
           {
               answer=Math.max(answer, prices[j] - prices[i]);
           }
       }
       return answer;
   }
   public static void main(String[] args) {
 
   int[] prices = {7, 1, 5, 3, 6, 4};
   System.out.println(maxProfit(prices));
   }
}

Complexity Analysis

Time Complexity

The time complexity of the above code is O(N^2) because we are traversing over all the pairs of the array.

Space Complexity

The space complexity of the above code is O(1) because we are not using any extra space.

Optimized Solution

Idea:

For every jth element, we will find the minimum element before it, so that we make the best pair for the jth element.

Code:

C++ Program of Best Time to Buy and Sell Stock:

#include <bits/stdc++.h>
using namespace std;
 
int maxProfit(vector<int> &prices)
{
   int answer = 0;
   int mi = INT_MAX;
   for (auto ele : prices)
   {
       answer = max(answer, ele - mi);
       mi = min(mi, ele);
   }
   return answer;
}
int main()
{
   vector<int> prices = {7, 1, 5, 3, 6, 4};
   cout << maxProfit(prices) << endl;
   return 0;
}

JAVA Program of Best Time to Buy and Sell Stock:

public class TutorialCup
{
   public static int maxProfit(int[] prices) {
        int answer = 0;
  int n=prices.length;
  int mi = Integer.MAX_VALUE;
  for (int i=0;i<n;i++)
  {
    answer = Math.max(answer, prices[i] - mi);
    mi = Math.min(mi,prices[i]);
  }
  return answer;
    }
   public static void main(String[] args) {
   int[] prices = {7, 1, 5, 3, 6, 4};
   System.out.println(maxProfit(prices));
   }
}

Complexity Analysis for Best Time to Buy and Sell Stock LeetCode Solution

Time Complexity

The time complexity of the above code is O(N) because we are traversing over the array only once.

Space Complexity

The space complexity of the above code is O(1) because we are not using any extra space.

References: https://en.wikipedia.org/wiki/Brute-force_search

https://download.java.net/java/GA/jdk14/docs/api/java.base/java/lang/reflect/Array.html