menu

### Best Time to Buy and Sell Stock

**Problem Statement:**

You are given an array `prices`

where `prices[i]`

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

day.^{th}

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`

.

##
Examples

Input:prices = [7,1,5,3,6,4]Output:5Explanation: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.

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

### Solutions

##
Brute Force Approach

##### Algorithm

Two loops enable us to oversee each transaction, facilitating the maintenance of a **max_profit** variable that retains the highest value achieved across all transactions.

##### Approach

- Use a for loop of ‘
`i`

’ from 0 to`n`

. - Use another for loop of
`j`

from ‘`i+1`

’ to`n`

. - If
`prices[j] > prices[i]`

, calculate the difference, compare, and store it in the`max_profit`

variable. - Return
`max_profit`

.

##### Code

` ````
```class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_profit = 0
n = len(prices)
for i in range(n):
for j in range(i + 1, n):
if prices[j] > prices[i]:
max_profit = max(prices[j] - prices[i], max_profit)
return max_profit

##### Input

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

##### Output

5

##### Time and Space Complexity

__Time Complexity:__ O(N** ^{2}**)

__Space Complexity:__ O(1) as we are not using any extra space.

##
Optimal Approach

##### Algorithm

We’ll sequentially `traverse`

the array, maintaining a `minimum`

from the array’s start. At each step, we’ll compare every `element`

with this `minimum`

. If an `element`

surpasses the `minimum`

, we’ll calculate the `difference`

and update the `maximum`

value; otherwise, we’ll refresh the `minimum`

value.

##### Approach

- Set a variable,
`max_profit`

, initially storing 0. - Set another variable,
`min_price`

, initially storing a larger value (e.g.,`MAX_VALUE`

). - Iterate through a for loop from 0 to n.
- Update
`min_price`

if it’s greater than the current element in the array. - Calculate the difference between
`min_price`

and the current array element, compare, and store it in`max_profit`

. - Finally, return the value stored in
`max_profit`

.

##### Short Video Explanation

For a better understanding of the algorithm, please watch the video by clicking on the button below.

##### Code

Refer the code below for better understanding.

` ````
```class Solution:
def maxProfit(self, prices: List[int]) -> int:
max_profit = 0
min_price = float("inf")
for i in range(len(prices)):
min_price = min(min_price, prices[i])
max_profit = max(max_profit, prices[i] - min_price)
return max_profit

##### Input

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

##### Output

5

##### Time and Space Complexity

__Time Complexity:__ O(N), where N = size of the given array.

__Space Complexity:__ O(1) as we are not using any extra space.

WhatsApp

Facebook

Twitter

LinkedIn

Email