DEV Community

Nishkarsh Pandey
Nishkarsh Pandey

Posted on

2 2 2 2 2

๐Ÿ“… Day 1/75 of LeetCode Practice โ€“ [Todayโ€™s Focus: Arrays / Strings / Sliding Window]::PART 2

๐Ÿ“ˆ 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[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 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
Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

๐Ÿ” 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:

NeetCode
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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

โœ๏ธ 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

Scale globally with MongoDB Atlas. Try free.

Scale globally with MongoDB Atlas. Try free.

MongoDB Atlas is the global, multi-cloud database for modern apps trusted by developers and enterprises to build, scale, and run cutting-edge applications, with automated scaling, built-in security, and 125+ cloud regions.

Learn More

Top comments (0)