Two Pointers

Use two pointers when you can decide the next move from the current pair of indices without needing to scan the middle.

• The array is sorted, or you are allowed to sort first.
• The question is a pair / triplet, a palindrome, or two ends.
• You must do it in place and keep order: compact, drop, or partition

Two pointers from opposite ends

l, r = 0, len(nums) - 1
while l < r:
    s = nums[l] + nums[r] 
    if s == target:
        return [l, r]
    if s < target:
        l+=1
    else:
        r-=1

3Sum

 
def threeSum(nums, target):
    nums.sort()
    n = len(nums)
    res = []
    for i in range(n):
        # skip duplicates
        if i and nums[i] == nums[i-1]:
            continue
        l, r = i+1, n-1
        while l < r:
            s = nums[i] + nums[l] + nums[r] 
            if s==0:
                res.append([nums[i], nums[l], nums[r]])
                l+=1
                r-=1
                while l<r and nums[l] == nums[l-1]:
                    l+=1
            elif s < 0:
                l+=1
            else:
                r-=1
    return res

Same direction read/write

• Copying the elements we keep to the front of the same array, instead of building a new list
  • “Remove … in place, return the new length”
  • “Move all X to the end, keep order of the rest”
  • “Overwrite the array so keepers are at the front”
  • “Do not use extra space” + the array is already in the order you care about (often sorted)

w=0
for x in nums:
    if keep(x):
        nums[w] = x # write it at the next free slot
        w+=1 # that slot is now taken
return w