# Leetcode 121: Best Time To Buy and Sell Stock

## Table of Contents

The Best time to buy and sell stock problem is a classic problem that can be solved using the Greedy approach. This is one of the most popular questions asked in such interviews.

Companies that have asked this in their coding interview are Facebook, Amazon, Apple, Netflix, Google, Microsoft, Adobe, and many more top tech companies.

## Problem Statement

You are given an array `prices`

where `prices[i]`

is the price of a given stock on the `i`

th day.

You want to maximize your profit by choosing a **single day** to buy one stock and choosing a **different day to sell that stock in the future**.

Return *the maximum profit you can achieve from this transaction*. If you cannot achieve any profit, return `0`

.

**Test case#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.
```

**Test case#2**

```
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
```

**Constraints**

1 <= prices.length <= 10^{5} (The prices array will have 1 to 100,000 elements in the array).

## Understanding the problem?

We know how stock markets are, and the question says, *Buy Low, Sell High. *So, we are given an input array containing integers, which are the price of stocks on a given day `i`

.

At any given time, we can only purchase one stock before selling it, and only then can we consider purchasing another stock. Our goal is to maximize profits from each transaction.

"Test-Case 1 clearly explains purchasing low-priced stocks and selling them for maximum profits."

*.*

*Don't forget to hit the like button and write a comment. It supports my website a lot*## Illustrations

```
Input: prices = [7,1,5,3,6,4]
Output: 5
```

When trading stocks, selling a stock on day one and buying it on day two is impossible. This goes against the basic principles of stock trading.

To maximize our profit, we can purchase the stock on the second day and sell it on the fifth day, then use the funds to purchase the stock with the highest value on the fifth day. The diagram below provides a visual representation of the maximum profit that can be obtained from the given array of stock prices.

As shown in the below figure, we are going to buy the stock on the day `2`

and sell on the day `5`

, which gives us the maximum profit of `6 - 1`

, i.e., `5`

.

## Thought process

My first thoughts when looking at this problem and the questions I have are:

- This is
`prices`

array, so I believe there are no negative prices? - What are the constraints? What if there's only a single element in the
`prices`

array? - What if the stock price on day 1 is high and on all other days is lower? Should I return
`0`

?

Once the above questions are discussed with the interviewer, I will propose different ways to solve this problem. The ones that come to my mind right now are:

- Brute force / Naive approach
- Using extra auxiliary Space
- One pass or Greedy approach

## Approach 1: Naive/Brute force

### Intuition

So, how will we keep track of the smallest and the largest numbers while traversing the array?

With this idea in mind, we can have two loops running, and the algorithmic steps are as follows.

### Algorithm

- Initialize a variable
`maxProfit`

to`0`

. This variable will be used to keep track of the maximum profit. - The outer loop represents the day on which you consider buying the stock. Iterate through each day as a potential buying day (
`buyDay`

) from`0`

to`prices.length - 1`

. - The inner loop represents the day on which you consider selling the stock. For each buying day (
`buyDay`

), iterate through the subsequent days as potential selling days (`sellDay`

) from the next day to the last day. - In the inner loop:
- Calculate the current profit by subtracting the price on the buying day (
`prices[buyDay]`

) from the price on the selling day (`prices[sellDay]`

), which can be`currentProfit = prices[sellDay] - prices[buyDay]`

- Now, update the
`maxProfit`

, by doing`maxProfit = Math.max(maxProfit, currentProfit)`

- Calculate the current profit by subtracting the price on the buying day (
- Continue the iterations, considering different buying and selling days.
- After completing both loops, return the final value of
`maxProfit`

.

```
class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0;
for (int buyDay = 0; buyDay < prices.length; buyDay += 1) {
for (int sellDay = buyDay + 1; sellDay < prices.length; sellDay += 1) {
int currentProfit = prices[sellDay] - prices[buyDay];
maxProfit = Math.max(maxProfit, currentProfit);
}
}
return maxProfit;
}
}
```

### Complexity Analysis

**Time complexity**: is `O(n^2)`

.

**Space complexity**: Space is `O(1)`

, Only variables are used here `maxProfit`

, `i`

, and `j`

. All these three variables store `4`

integer bytes and their values are updated on each iteration. So the total space occupied are `3 * 4 = 12`

bytes, which is constant.

## Using auxiliary space

### Intuition

This approach is not recommended because we use extra space to store an auxiliary array. Can we do better than this? 🤔

Yes, a better approach uses linear search through the array. This is for your practice.

### Algorithm

- Create an auxiliary array
`aux`

of the same length as the prices array. Store the maximum right-side stock price at each of these indexes. - Initialize the last element of the
`aux`

array (`aux[prices.length - 1]`

) with the last price in the prices array (`prices[prices.length - 1]`

). Because this is the max price and there are no right elements. - Iterate backward through the prices array, starting from the
`prices.length - 2`

to`0`

.- For each index
`i`

, set`aux[i]`

to the maximum value between the current price (`prices[i]`

) and the next day's maximum price (`aux[i + 1]`

).

- For each index
- Initialize a variable
`profit`

to`0`

. This variable will be used to keep track of the maximum profit. - Iterate through each day in the prices array.
- For each day (
`i`

):- Calculate the current profit by subtracting the current price (
`prices[i]`

) from the pre-calculated maximum price (`aux[i]`

), using`currProfit = aux[i] - prices[i]`

- Calculate the current profit by subtracting the current price (

- For each day (
- Update
`profit`

with the maximum of its current value and the calculated`currProfit`

using`profit = Math.max(currProfit, profit)`

- After completing the iteration, return the final value of
`profit`

.

```
class Solution {
public int maxProfit(int[] prices) {
int[] aux = new int[prices.length];
aux[prices.length - 1] = prices[prices.length - 1];
for (int i = aux.length - 2; i >= 0; i--) {
aux[i] = Math.max(prices[i], aux[i + 1]);
}
int profit = 0;
for (int i = 0; i < prices.length; i++) {
int currProfit = aux[i] - prices[i];
profit = Math.max(currProfit, profit);
}
return profit;
}
}
```

### Complexity Analysis

**Time complexity**: Time is `O(N)`

, where `N`

is the number of elements in the prices array.

**Space complexity**: Space is `O(N)`

, we used an auxiliary array to store the max stock on the right side of each price array element.

## One pass [Greedy approach]

### Intuition

We used auxiliary or extra space for the max elements to the element's right. But that takes an order `N`

space, which is not at all recommended, plus a bad approach.

Here we keep track of the lowest left price and find the difference between largest price & lowest price.

We are greedy and buy the lowest stocks in a day and sell them for higher profits in the future.

### Algorithm

- Initialize
`minprice`

to`Integer.MAX_VALUE`

and`maxprofit`

to`0`

. These variables will be used to keep track of the minimum price and maximum profit. - Iterate through each day in the prices array.
- For each day (
`i`

):- If the current price (
`prices[i]`

) is less than`minprice`

, update`minprice`

to the current price. - Else, if the difference between the current price and
`minprice`

is greater than`maxprofit`

, update`maxprofit`

with this difference.

- If the current price (

- For each day (
- After completing the iteration, return the final value of
`maxprofit`

.

```
class Solution {
public int maxProfit(int prices[]) {
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < minprice) {
minprice = prices[i];
} else if (prices[i] - minprice > maxprofit) {
maxprofit = prices[i] - minprice;
}
}
return maxprofit;
}
}
```

```
// Refactoring above code for readability
class Solution {
public int maxProfit(int[] prices) {
int maxProfit = 0;
int minPrice = Integer.MAX_VALUE;
for (int price : prices) {
if (price < minPrice)
minPrice = price;
else
maxProfit = Math.max(maxProfit, price - minPrice);
}
return maxProfit;
}
}
```

### Complexity Analysis

**Time complexity**: Time is `O(N)`

, where `N`

is the number of elements in the prices array.

**Space complexity**: Space is `O(1)`

.

## Gopi Gorantala Newsletter

Join the newsletter to receive the latest updates in your inbox.