## DEV Community

Abhishek Chaudhary

Posted on

# Best Time to Buy and Sell Stock

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.

Example 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 <= 105`
• `0 <= prices[i] <= 104`

SOLUTION:

``````# class Solution:
#     def maxProfit(self, prices: List[int]) -> int:
#         valIndex = {}
#         maxProfit = 0
#         for i, price in enumerate(prices):
#             if price not in valIndex:
#                 valIndex[price] = [i, i]
#             else:
#                 valIndex[price][1] = i
#         newprices = sorted(valIndex.keys())
#         n = len(newprices)
#         for j in range(n - 1, -1, -1):
#             end = newprices[j]
#             if end - newprices[0] <= maxProfit:
#                 break
#             for i in range(j):
#                 curr = end - newprices[i]
#                 if curr <= maxProfit:
#                     break
#                 if valIndex[end][1] > valIndex[newprices[i]][0]:
#                     maxProfit = max(maxProfit, curr)
#         return maxProfit

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