all topics

Sliding Window

Contains Duplicate II

Check if two equal values exist within k indices of each other. [1,2,3,1], k = 3 → True.

Sliding window of size k

  • Keep a set of the values in the current window.
  • Window grows past size k → remove the oldest element (nums[l]) before adding the new one, so the set never holds more than k values.
  • Current number's already in the window → found a duplicate within range.
python
class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        window = set()
        l = 0
 
        for r in range(len(nums)):
            if r-l > k:
                window.remove(nums[l])
                l+=1
            if nums[r] in window:
                return True
            window.add(nums[r])
        return False
timeO(n)spaceO(min(n, k))

Best Time to Buy and Sell Stock

One transaction only, buy once and sell once, maximize profit. [7,1,5,3,6,4] → 5 (buy at 1, sell at 6).

Track the minimum seen so far

  • Walk through the prices once, keeping the lowest price seen so far.
  • At each price, check the profit from selling today (price - min_price) and keep the best one.
python
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        
        min_price = float('inf')
        max_profit = 0
 
        for price in prices:
            min_price = min(price, min_price)
            profit = price - min_price
            max_profit = max(profit, max_profit)
 
        return max_profit
timeO(n)spaceO(1)

Longest Substring Without Repeating Characters

Find the length of the longest substring of s with no repeated characters. "abcabcbb" → 3 ("abc").

Sliding window, shrink on repeat

  • Grow the window by moving r forward, adding each character to a set.
  • Hit a character already in the window → shrink from the left (l), removing characters, until the repeat is gone.
  • Track the widest window seen.
python
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        l = 0
        longest = 0
        sett = set()
        n = len(s)
 
        for r in range(n):
            while s[r] in sett:
                sett.remove(s[l])
                l += 1
 
            w = (r - l) + 1
            longest = max(longest, w)
            sett.add(s[r])
 
        return longest
timeO(n)spaceO(min(n, charset))

Longest Repeating Character Replacement

You can change up to k characters in s. Find the longest substring you can turn into all the same character. s = "AABABBA", k = 1 → 4.

Sliding window, track the most frequent letter

  • Grow the window, counting letter frequencies as you go.
  • Window's invalid once (window size) - (count of its most frequent letter) > k, meaning more than k characters would need replacing. Shrink from the left until it's valid again.
  • Track the widest window seen.
python
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        longest = 0
        l = 0
        counts = [0] * 26
 
        for r in range(len(s)):
            counts[ord(s[r]) - 65] += 1
 
            while (r - l + 1) - max(counts) > k:
                counts[ord(s[l]) - 65] -= 1
                l += 1
 
            longest = max(longest, (r - l + 1))
 
        return longest
timeO(n)spaceO(1)

Permutation in String

Check whether s2 contains a permutation (any letter rearrangement) of s1 as a contiguous substring. s1 = "ab", s2 = "eidbaooo" → True (contains "ba").

Fixed-size sliding window, compare letter counts

  • Count the letters in s1, and in the first window of s2 (same length as s1).
  • Same counts → found a permutation.
  • Otherwise slide the window forward one character at a time: add the letter entering, remove the one leaving, compare again.
python
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        n1 = len(s1)
        n2 = len(s2)
 
        if n1 > n2:
            return False
 
        s1_counts = [0] * 26
        s2_counts = [0] * 26
 
        for i in range(n1):
            s1_counts[ord(s1[i]) - 97] += 1
            s2_counts[ord(s2[i]) - 97] += 1
 
        if s1_counts == s2_counts:
            return True
 
        for i in range(n1, n2):
            s2_counts[ord(s2[i]) - 97] += 1
            s2_counts[ord(s2[i - n1]) - ord('a')] -= 1
 
            if s1_counts == s2_counts:
                return True
 
        return False
timeO(n)spaceO(1)

Minimum Size Subarray Sum

Find the length of the shortest contiguous subarray whose sum is at least target. Return 0 if none exists. target = 7, nums = [2,3,1,2,4,3] → 2 ([4,3]).

Sliding window, shrink while still valid

  • Grow the window by adding nums[r] to a running sum.
  • Sum's at least target → the window is a valid candidate. Record its length, then shrink from the left (subtracting nums[l]) as long as it's still valid, chasing the smallest window.
  • No valid window ever found → return 0.
python
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        min_length = float('inf')
        summ = 0
        l = 0
 
        for r in range(len(nums)):
            summ += nums[r]
 
            while summ >= target:
                min_length = min(min_length, r - l + 1)
                summ -= nums[l]
                l += 1
 
        return min_length if min_length < float('inf') else 0
timeO(n)spaceO(1)