Two Pointers / Sliding Window

Given a string s, return True if it is a palindrome after converting all uppercase letters to lowercase and removing all non-alphanumeric characters, otherwise return False.

Use Two Pointers starting at both ends of the string. Move l forward and r backward, skipping any non-alphanumeric characters. If the lowercase characters at both pointers differ, the string is not a palindrome. This avoids building a cleaned copy of the string, so extra space stays constant.

def isPalindrome(s: str) -> bool:
    l, r = 0, len(s) - 1
    while l < r:
        while l < r and not s[l].isalnum():
            l += 1
        while l < r and not s[r].isalnum():
            r -= 1
        if s[l].lower() != s[r].lower():
            return False
        l += 1
        r -= 1
    return True
    

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers.

Sort the array first. Fix one element nums[i], then use the Two-Pointer approach (l and r) on the remaining part. If the current sum is smaller than target, move l right to increase it; if larger, move r left to decrease it. Update the closest sum whenever \(|\text{sum} - \text{target}|\) improves, and return immediately if the sum equals target.

def threeSumClosest(nums: list[int], target: int) -> int:
    nums.sort()
    closest = nums[0] + nums[1] + nums[2]
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        l, r = i + 1, len(nums) - 1
        while l < r:
            total = nums[i] + nums[l] + nums[r]
            if abs(total - target) < abs(closest - target):
                closest = total
            if total < target:
                l += 1
            elif total > target:
                r -= 1
            else:
                return total
    return closest
    

Given \(n\) non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Water above a bar is \(\min(\text{maxLeft}, \text{maxRight}) - \text{height}[i]\). Instead of precomputing prefix and suffix arrays, use Two Pointers with running left_max and right_max. Always process the side with the smaller maximum, because that side's water level is limited by its own maximum no matter what lies on the other side. Move that pointer inward, update its maximum, and add the trapped water.

def trap(height: list[int]) -> int:
    if not height:
        return 0
    l, r = 0, len(height) - 1
    left_max, right_max = height[l], height[r]
    water = 0
    while l < r:
        if left_max < right_max:
            l += 1
            left_max = max(left_max, height[l])
            water += left_max - height[l]
        else:
            r -= 1
            right_max = max(right_max, height[r])
            water += right_max - height[r]
    return water
    

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. Return the number of unique elements k, with the first k elements of nums holding the unique values in order.

Use a slow and fast pointer. The fast pointer i scans the array, while the slow pointer k marks the next position to write a unique value. Because the array is sorted, a value is new only if it differs from the last unique value written (nums[k - 1]).

def removeDuplicates(nums: list[int]) -> int:
    if not nums:
        return 0
    k = 1
    for i in range(1, len(nums)):
        if nums[i] != nums[k - 1]:
            nums[k] = nums[i]
            k += 1
    return k
    

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements. This must be done in-place without making a copy of the array.

Keep a write pointer k that marks where the next non-zero element belongs. Scan the array with i; whenever nums[i] is non-zero, swap it with nums[k] and advance k. Everything before k is always non-zero and in original order, and the zeroes get pushed to the end. This does the minimum number of writes in a single pass.

def moveZeroes(nums: list[int]) -> None:
    k = 0
    for i in range(len(nums)):
        if nums[i] != 0:
            nums[k], nums[i] = nums[i], nums[k]
            k += 1
    

Given a string s, find the length of the longest substring without repeating characters.

Use a Sliding Window with a hash map storing the last index at which each character was seen. Expand the window by moving right. If the current character was last seen inside the window (last[ch] >= left), jump left directly to one position after that index instead of shrinking one step at a time. Track the maximum window size. Here \(\Sigma\) is the size of the character set.

def lengthOfLongestSubstring(s: str) -> int:
    last = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best
    

Given two strings s and t of lengths \(M\) and \(N\), return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If no such substring exists, return an empty string.

Use a Sliding Window with a single need counter built from t and a missing variable that counts how many required characters are still absent. Expanding right decrements need[ch], and missing only drops when the count was positive (a useful character). Once missing == 0, the window is valid: shrink from the left while the leftmost character is surplus (need[s[left]] < 0), record the best window, then drop one required character to start searching for the next window. Each index enters and leaves the window at most once.

from collections import Counter

def minWindow(s: str, t: str) -> str:
    if not t or len(t) > len(s):
        return ""
    need = Counter(t)
    missing = len(t)
    left = 0
    best_start, best_len = 0, float('inf')

    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1

        if missing == 0:
            # Shrink while the left character is surplus
            while need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            if right - left + 1 < best_len:
                best_start, best_len = left, right - left + 1
            # Drop one required character to look for the next window
            need[s[left]] += 1
            missing += 1
            left += 1

    return "" if best_len == float('inf') else s[best_start:best_start + best_len]
    

Given a string s of uppercase English letters and an integer k, you can replace at most k characters with any other character. Return the length of the longest substring containing the same letter after performing these replacements.

A window is valid if \(\text{window size} - \text{max frequency} \le k\), meaning the characters that are not the most frequent one can all be replaced. Expand right while counting characters and tracking max_freq. If the window becomes invalid, shrink it by one from the left. Note that max_freq is never decreased: the answer can only improve when a larger frequency is found, so a stale value never produces a wrong result. The space is \(O(1)\) because the alphabet has only 26 letters.

def characterReplacement(s: str, k: int) -> int:
    count = {}
    left = 0
    max_freq = 0
    best = 0
    for right, ch in enumerate(s):
        count[ch] = count.get(ch, 0) + 1
        max_freq = max(max_freq, count[ch])

        if (right - left + 1) - max_freq > k:
            count[s[left]] -= 1
            left += 1

        best = max(best, right - left + 1)
    return best
    

Given two strings s1 and s2, return True if s2 contains a permutation of s1, or False otherwise. In other words, return True if one of s1's permutations is a substring of s2.

A permutation has the same character counts as s1, so slide a fixed-size window of length len(s1) over s2 and compare 26-letter frequency arrays. Instead of comparing the arrays at every step, maintain a matches counter, the number of letters whose counts are equal. When a character enters or leaves the window, only that one letter's status can change, so matches is updated in \(O(1)\). A window is a permutation when matches == 26.

def checkInclusion(s1: str, s2: str) -> bool:
    n1, n2 = len(s1), len(s2)
    if n1 > n2:
        return False

    cnt1, cnt2 = [0] * 26, [0] * 26
    for i in range(n1):
        cnt1[ord(s1[i]) - ord('a')] += 1
        cnt2[ord(s2[i]) - ord('a')] += 1

    matches = sum(cnt1[i] == cnt2[i] for i in range(26))

    for r in range(n1, n2):
        if matches == 26:
            return True

        # Character entering the window
        i = ord(s2[r]) - ord('a')
        cnt2[i] += 1
        if cnt2[i] == cnt1[i]:
            matches += 1
        elif cnt2[i] == cnt1[i] + 1:
            matches -= 1

        # Character leaving the window
        i = ord(s2[r - n1]) - ord('a')
        cnt2[i] -= 1
        if cnt2[i] == cnt1[i]:
            matches += 1
        elif cnt2[i] == cnt1[i] - 1:
            matches -= 1

    return matches == 26
    

Given an integer array nums and a sliding window of size k moving from the far left to the far right, return the maximum value in each window position.

Use a Monotonic Decreasing Deque that stores indices. Before adding index i, pop from the back every index whose value is <= nums[i], since those elements can never be a window maximum while nums[i] is in the window. Pop from the front if its index has left the window (<= i - k). The front of the deque is always the index of the current maximum. Each index is pushed and popped at most once, giving \(O(N)\) total time.

from collections import deque

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    dq = deque()  # indices, values in decreasing order
    res = []
    for i, num in enumerate(nums):
        # Remove smaller elements from the back
        while dq and nums[dq[-1]] <= num:
            dq.pop()
        dq.append(i)

        # Remove the front index if it is out of the window
        if dq[0] <= i - k:
            dq.popleft()

        # Window is fully formed
        if i >= k - 1:
            res.append(nums[dq[0]])
    return res