← All topics

Two Pointers

Instead of nesting loops over an array, walk two indices toward (or away from) each other, using the sortedness or structure of the input to rule out whole ranges at a time. A huge fraction of O(n^2)-looking problems collapse to O(n) this way.

Easy reps

125. Valid Palindrome

Given a string s, return true if it is a palindrome, considering only alphanumeric characters and ignoring case.

def is_palindrome(s):
    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

One pointer starts at each end and they march toward the middle, skipping non-alphanumeric characters along the way. Any mismatch short-circuits immediately -- no need to build a cleaned-up copy of the string first.

88. Merge Sorted Array

nums1 and nums2 are sorted arrays; nums1 has extra trailing space to hold the result. Merge nums2 into nums1 in place, sorted.

def merge(nums1, m, nums2, n):
    i, j, write = m - 1, n - 1, m + n - 1
    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[write] = nums1[i]
            i -= 1
        else:
            nums1[write] = nums2[j]
            j -= 1
        write -= 1

Merging from the front would overwrite values in nums1 before you've read them. Filling from the back instead -- three pointers, always placing the larger of the two current candidates -- avoids that entirely and needs no extra array.

Level up

Same topic, no training wheels. Solve these on your own before you check the editorial.