# Best Time to Buy and Sell Stock LeetCode Solution

Frequently asked in Adobe Amazon Apple BlackRock Bloomberg ByteDance Cisco Citadel Expedia Facebook Goldman Sachs Google JPMorgan Microsoft Netflix Nvidia Oracle Paytm Salesforce ServiceNow Snapchat Uber Visa VMware Yahoo Zoho
LeetCode LeetCodeSolutions Riot GamesViews 1737

## 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]
```
`5`

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]`
` 0`

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();
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
}
}
}
int main()
{
vector<int> prices = {7, 1, 5, 3, 6, 4};
cout << maxProfit(prices) << endl;
return 0;
}
```
`5`

### JAVA Program of Best Time to Buy and Sell Stock:

```public class TutorialCup
{
public static int maxProfit(int[] prices)
{
int n = prices.length;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
}
}
}
public static void main(String[] args) {

int[] prices = {7, 1, 5, 3, 6, 4};
System.out.println(maxProfit(prices));
}
}
```
`5`

## 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 mi = INT_MAX;
for (auto ele : prices)
{
mi = min(mi, ele);
}
}
int main()
{
vector<int> prices = {7, 1, 5, 3, 6, 4};
cout << maxProfit(prices) << endl;
return 0;
}
```
`5`

### JAVA Program of Best Time to Buy and Sell Stock:

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

## 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.