Two Pointers

Two Pointers Technique

# Two pointers on sorted array -- O(n)

# Two Sum (sorted)
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr)-1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if   s == target: return [lo, hi]
        elif s <  target: lo += 1
        else:             hi -= 1
    return []

# Container with most water
def max_water(height):
    lo, hi = 0, len(height)-1
    best = 0
    while lo < hi:
        water = (hi-lo) * min(height[lo], height[hi])
        best  = max(best, water)
        if height[lo] < height[hi]: lo += 1
        else:                        hi -= 1
    return best

# Remove duplicates from sorted array (in-place)
def remove_dups(nums):
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

# 3Sum
def three_sum(nums):
    nums.sort()
    result = []
    for i in range(len(nums)-2):
        if i>0 and nums[i]==nums[i-1]: continue
        lo, hi = i+1, len(nums)-1
        while lo < hi:
            s = nums[i]+nums[lo]+nums[hi]
            if s==0: result.append([nums[i],nums[lo],nums[hi]]); lo+=1; hi-=1
            elif s<0: lo+=1
            else: hi-=1
    return result