Sliding Window is used for finding the length of a subarray or directly returning the subarray that meet certain conditions. (We can use a variable to track the length if returning the subarray is not needed.)

vs Prefix

For problems involving the sum, product, or average of a subarray that must meet a target, both the Sliding Window and Prefix Sum approaches may be applicable.

• Sliding Window
  • When array contains only positive numbers, only negative numbers, or numbers are sorted, allowing O(n) complexity by expanding and contracting the window dynamically.
  • We can not use Sorting algorithms because that will change the array (change the question) then change the subarray answer.
• Prefix Sum:
  • It can handle both positive and negative numbers or is unordered.
  • This approach requires O(n) space and may take O(n²) time if we check all subarrays.
  • However, if the problem involves finding a subarray sum “equal to” a target, we can use a HashMap to track prefix sums, reducing time complexity to O(n).

⭐️ (Easy) 121. Best Time to Buy and Sell Stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock

Last review: Aug 16, 2025 Next review: It was cool.

We must buy the stock first then sell it. We can not go back to the past to sell the stock earlier than the buying time.

Compare to ⭐️ (Medium) 122. Best Time to Buy and Sell Stock II, NeetCode 250 this question only allows buying and selling once.

Brutal Force

When we find a better buying point, from there, we don’t need the the current buying price compare with future prices, cause it is better to use the better buying point to compare with.

• Time Complexity O(n*(n+1)/2) = O(n^2)
• Space Complexity O(1)

func maxProfit(prices []int) int {
    var profit int
    for L := 0; L < len(prices); L++ {
        for R := L + 1; R < len(prices); R++ {
            profit = max(profit, prices[R]-prices[L])
        }
    }
    return profit
}

Sliding Window

The window means the range we hole the stock:

1. If the R finds a lower price than current buying point (L), meaning current L has visited all of its potential selling points since we can use the better starting point to compare with future selling points.
2. Even though we find a better buying point, but the selling points might be higher in the past, but we can not go back. Hence we track the maximum profit along the process.

• Time Complexity O(n)