Two Pointers

Remove Element

Remove every occurrence of val from nums in place, return the new length. nums = [3,2,2,3], val = 3 → length 2.

Swap-and-shrink

i scans forward from the start, n tracks how much of the array is still "in play".
nums[i] == val → overwrite it with nums[n-1], shrink n by 1, don't move i (the swapped-in value still needs checking).
Otherwise → just move i forward.
n is the final length once i catches up to it.

python

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        n = len(nums)
 
        while i < n:
            if nums[i] == val:
                nums[i] = nums[n-1]
                n-=1
            else:
                i+=1
        
        return n

timeO(n)spaceO(1)

Sort Colors

Sort an array of 0s, 1s, and 2s in place, without a library sort. [2,0,2,1,1,0] → [0,0,1,1,2,2].

Count, then overwrite

Count how many 0s, 1s, and 2s there are, one pass.
Overwrite the array in three chunks, in order: all the 0s, then all the 1s, then all the 2s.

python

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        counts = [0, 0, 0]
 
        for color in nums:
            counts[color] += 1
 
        R,W,B = counts
 
        nums[:R] = [0] * R
        nums[R:R+W] = [1] * W
        nums[R+W:] = [2] * B

timeO(n)spaceO(1)

Reverse String

Reverse the array of characters s in place. ["h","e","l","l","o"] → ["o","l","l","e","h"].

1. Built-in reverse

Python's list reverse() does it in place, one call.

python

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s.reverse()

timeO(n)spaceO(1)

2. Two-pointer swap

l starts at the front, r starts at the back.
Swap s[l] and s[r], then move l forward and r back.
Stop once they meet in the middle.

python

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        l,r = 0, len(s) - 1
        while l < r:
            s[l], s[r] = s[r], s[l]
            l += 1
            r -=1

timeO(n)spaceO(1)

Valid Palindrome

Check whether s is a palindrome, ignoring case and non-alphanumeric characters. "A man, a plan, a canal: Panama" → True.

Two pointers, skip non-alphanumeric

l starts at the front, r starts at the back.
Skip past any character that isn't a letter or digit, on either side.
Compare the two characters, case-insensitive. Mismatch → not a palindrome.
Move both pointers inward, stop once they meet.

python

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

timeO(n)spaceO(1)

Valid Palindrome II

Check whether s can become a palindrome by deleting at most one character. "abca" → True (remove c or b).

Two pointers, skip one mismatch

Walk in from both ends like a normal palindrome check.
First mismatch → try skipping the left character, or try skipping the right character, and check if either remainder is a full palindrome on its own.
No mismatch the whole way through → already a palindrome, no deletion needed.

python

class Solution:
    def validPalindrome(self, s: str) -> bool:
        
        def is_palindrome(l, r):
            while l < r:
                if s[l] != s[r]:
                    return False
                l += 1
                r -= 1
            return True
 
        left, right = 0, len(s) - 1
 
        while left < right:
            if s[left] != s[right]:
                return is_palindrome(left + 1, right) or is_palindrome(left, right - 1)
            left += 1
            right -= 1
 
        return True

timeO(n)spaceO(1)

Merge Strings Alternately

Merge word1 and word2 by alternating characters; once one runs out, tack on the rest of the other. word1 = "abc", word2 = "pqr" → "apbqcr".

Walk both strings together

Walk an index i up to the length of the longer string.
word1 still has a character at i → append it. Same check for word2.
Join everything at the end.

python

class Solution:
    def mergeAlternately(self, word1: str, word2: str) -> str:
        n, m = len(word1), len(word2)
        res = []
        for i in range(max(m, n)):
            if i < n:
                res.append(word1[i])
            if i < m:
                res.append(word2[i])
        return "".join(res)

timeO(n+m)spaceO(n+m)

Merge Sorted Array

Merge nums2 into nums1 in place; nums1 has m real elements followed by n empty slots to fill. nums1 = [1,2,3,0,0,0], m=3, nums2 = [2,5,6], n=3 → [1,2,2,3,5,6].

Merge from the back

Three pointers: x at the end of nums1's real elements, y at the end of nums2, z at the very end of nums1 (the next slot to fill).
Place the bigger of nums1[x] / nums2[y] at nums1[z], then move that pointer back.
nums1 runs out first → whatever's left in nums2 is already sorted and smaller, drop it straight in.
nums2 runs out first → nums1's remaining values are already exactly where they need to be, nothing left to do.

python

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
 
        x, y = m - 1, n - 1
 
        for z in range(m + n - 1, -1, -1):
            if x < 0:
                nums1[z] = nums2[y]
                y -= 1
            elif y < 0:
                break
            elif nums1[x] > nums2[y]:
                nums1[z] = nums1[x]
                x -= 1
            else:
                nums1[z] = nums2[y]
                y -= 1

timeO(m+n)spaceO(1)

Remove Duplicates from Sorted Array

Remove duplicates from a sorted array in place, return the new length. [1,1,2,2,3] → length 3, with [1,2,3,...] in the first three spots.

Two pointers, write only when it changes

j tracks where the next unique value should go, i scans forward.
nums[i] differs from nums[i-1] → it's a new value, write it at nums[j] and bump j.
Otherwise → it's a duplicate, skip it.
j is the final length once the scan's done.

python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        n = len(nums)
        j = 1
        
        for i in range(1, n):
            if nums[i] != nums[i-1]:
                nums[j] = nums[i]
                j += 1
            
        return j

timeO(n)spaceO(1)

Two Sum II - Input Array Is Sorted

Find two numbers in a sorted array numbers that add up to target, return their 1-indexed positions. numbers = [2,7,11,15], target = 9 → [1,2].

Two pointers, converge from both ends

l starts at the front, r at the back.
Sum too small → move l forward, need a bigger number.
Sum too big → move r back, need a smaller number.
Sum matches → return both positions, 1-indexed.

python

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        l,r = 0, n - 1
 
        while l < r:
            summ = numbers[l] + numbers[r]
 
            if summ == target:
                return [l + 1, r + 1]
            elif summ < target:
                l += 1
            else:
                r -= 1

timeO(n)spaceO(1)

Container With Most Water

Pick two lines from height that, with the x-axis, hold the most water. Return that max area. [1,8,6,2,5,4,8,3,7] → 49.

Two pointers, always move the shorter side

l starts at the front, r at the back.
Area at any point is width × min(height[l], height[r]), track the max seen.
Move whichever pointer points at the shorter line, inward. The taller line can't help without a taller partner anyway, so it's never worth moving it first.

python

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        l = 0
        r = n - 1
        max_area = 0
 
        while l < r:
            w = r - l
            h = min(height[l], height[r])
            a = w * h
            max_area = max(max_area, a)
 
            if height[l] < height[r]:
                l += 1
            else:
                r -= 1
 
        return max_area

timeO(n)spaceO(1)

Boats to Save People

Each boat carries at most 2 people and a total weight up to limit. Find the fewest boats needed to carry everyone. people = [3,2,2,1], limit = 3 → 3.

Sort, pair lightest with heaviest

Sort everyone by weight.
r (heaviest remaining) always takes a boat, whether or not anyone joins them.
If the lightest remaining person (l) and the heaviest together fit under limit, they share that boat.
Every loop iteration uses exactly one boat, so boats just counts iterations.

python

class Solution:
    def numRescueBoats(self, people: List[int], limit: int) -> int:
        people.sort()
        boats = 0
        l,r = 0, len(people)-1
        while l<=r:
            if people[l] + people[r] <= limit:
                l+=1
            r-=1
            boats+=1
        return boats

timeO(n log n)spaceO(1)

3Sum

Find all unique triplets in nums that sum to zero. [-1,0,1,2,-1,-4] → [[-1,-1,2],[-1,0,1]].

Sort, then two pointers per fixed first number

Sort nums first, duplicates end up next to each other and small values come first.
Fix nums[i] as the first number of the triplet, skipping repeats of the same value to avoid duplicate triplets, then two-pointer search the rest of the array for a pair summing to -nums[i].
Found a match → record it, then skip past any duplicate values on both sides before continuing.
Sum too small → move lo up. Too big → move hi down.

python

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        answer = []
 
        for i in range(n):
            if nums[i] > 0:
                break
 
            if i > 0 and nums[i] == nums[i - 1]:
                continue
 
            lo, hi = i + 1, n - 1
 
            while lo < hi:
                summ = nums[i] + nums[lo] + nums[hi]
 
                if summ == 0:
                    answer.append([nums[i], nums[lo], nums[hi]])
 
                    lo, hi = lo + 1, hi - 1
 
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1
 
                    while lo < hi and nums[hi] == nums[hi + 1]:
                        hi -= 1
 
                elif summ < 0:
                    lo += 1
 
                else:
                    hi -= 1
 
        return answer

timeO(n^2)spaceO(1)