Оффлайн
- Регистрация
- 1 Мар 2015
- Сообщения
- 1,481
- Баллы
- 155
? Best Time to Buy and Sell Stock – (LeetCode #121)
In this post, I’ll walk through one of the most popular array-based problems on LeetCode — Best Time to Buy and Sell Stock — and how the Sliding Window pattern gives us a clean and efficient solution.
? Problem
You're given an array prices where prices 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 a different day in the future to sell that stock.
Return the maximum profit you can achieve. If you can’t achieve any profit, return 0.
? Example:
Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5
# Buy on day 1 (price = 1), sell on day 4 (price = 6), profit = 6 - 1 = 5
Python Code:
def maxProfit(prices):
min_price = float('inf') # Start with the highest possible value
max_profit = 0 # No profit yet
for price in prices:
# If we find a lower price, update min_price
if price < min_price:
min_price = price
else:
# Calculate profit and update max_profit if it’s higher
profit = price - min_price
max_profit = max(max_profit, profit)
return max_profit
Approach 2 :Using two pointers
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# Using the approach of two pointers
l,r=0,1#Left=>Buy and Right=>sell
maxProfit=0
while r<len(prices):
if prices[l]<prices[r]:
#Buy low and sell hight=Profit
profit=prices[r]-prices[l]
maxProfit=max(maxProfit,profit)
else:
l=r
r+=1
return maxProfit
? Explanation
We use two pointers:
l to track the buy day
r to track the sell day
If prices[r] > prices[l], we calculate profit and update the maximum.
If prices[r] <= prices[l], we found a lower buy price — move the left pointer to r.
Time Complexity:
O(n) — Single pass through the array.
? Space Complexity:
O(1) — No extra space needed.
Image Visualization:
Learned that form NeetCode
Maximum Subarray:
Leetcode(53)
? Problem Statement
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum, and return its sum.
? Example
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
# Explanation: [4,-1,2,1] has the largest sum = 6
Intuition
At every index, we decide:
Should we start a new subarray?
Or should we extend the current one?
We only keep extending when it gives us a better sum.
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
maxsub=nums[0]
curr_sub=0
for n in nums:
if curr_sub<0:
#ie Negative
curr_sub=0
curr_sub+=n
maxsub=max(maxsub,curr_sub)
return maxsub
What I Learned
This problem taught me:
How to reduce a brute force O(n^2) solution to O(n)
The importance of tracking state efficiently
That writing blogs helps lock in these concepts ?
? Related Problems
Maximum Product Subarray
Contiguous Array (binary nums)
House Robber
In this post, I’ll walk through one of the most popular array-based problems on LeetCode — Best Time to Buy and Sell Stock — and how the Sliding Window pattern gives us a clean and efficient solution.
? Problem
You're given an array prices where prices 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 a different day in the future to sell that stock.
Return the maximum profit you can achieve. If you can’t achieve any profit, return 0.
? Example:
Input: prices = [7, 1, 5, 3, 6, 4]
Output: 5
# Buy on day 1 (price = 1), sell on day 4 (price = 6), profit = 6 - 1 = 5
Python Code:
def maxProfit(prices):
min_price = float('inf') # Start with the highest possible value
max_profit = 0 # No profit yet
for price in prices:
# If we find a lower price, update min_price
if price < min_price:
min_price = price
else:
# Calculate profit and update max_profit if it’s higher
profit = price - min_price
max_profit = max(max_profit, profit)
return max_profit
Approach 2 :Using two pointers
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# Using the approach of two pointers
l,r=0,1#Left=>Buy and Right=>sell
maxProfit=0
while r<len(prices):
if prices[l]<prices[r]:
#Buy low and sell hight=Profit
profit=prices[r]-prices[l]
maxProfit=max(maxProfit,profit)
else:
l=r
r+=1
return maxProfit
? Explanation
We use two pointers:
l to track the buy day
r to track the sell day
If prices[r] > prices[l], we calculate profit and update the maximum.
If prices[r] <= prices[l], we found a lower buy price — move the left pointer to r.
Time Complexity:O(n) — Single pass through the array.
? Space Complexity:
O(1) — No extra space needed.
Image Visualization:
Learned that form NeetCode
Maximum Subarray:
Leetcode(53)
? Problem Statement
Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum, and return its sum.
? Example
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
# Explanation: [4,-1,2,1] has the largest sum = 6
Intuition
At every index, we decide:
Should we start a new subarray?
Or should we extend the current one?
We only keep extending when it gives us a better sum.
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
maxsub=nums[0]
curr_sub=0
for n in nums:
if curr_sub<0:
#ie Negative
curr_sub=0
curr_sub+=n
maxsub=max(maxsub,curr_sub)
return maxsub
What I LearnedThis problem taught me:
How to reduce a brute force O(n^2) solution to O(n)
The importance of tracking state efficiently
That writing blogs helps lock in these concepts ?
? Related Problems
Maximum Product Subarray
Contiguous Array (binary nums)
House Robber