Leetcode Pattern: 2 Pointers

TL;DR

Create 2 pointers -> Move 2 pointers until not valid (using while loop)

How to study

1. Familiarize all 4 patterns by solving a Leetcode question for each pattern.

Pattern #1: Pointers from both end

167. Two Sum II - Input Array Is Sorted

def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # Pointers from both end
        l, r = 0, len(numbers) - 1

        while l < r:
            curSum = numbers[l] + numbers[r]

            if curSum > target:
                r -= 1
            elif curSum < target:
                l += 1
            else:
                return [l+1, r+1]
        return []

Pattern #2: Slow and fast pointers

141. Linked List Cycle

def hasCycle(self, head: Optional[ListNode]) -> bool:
        # slow and fast pointer
        slow, fast = head, head

        # if fast pointer null, it reaches the end, no cycle
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                return True
        return False

Pattern #3: Merge 2 arrays using pointers

88. Merge Sorted Array

def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # m is array 1 pointer
        # n is array 2 pointer
        # last pointer
        last = m + n - 1

        # continue merging in reverse order until one array empty
        while m > 0 and n > 0:
            if nums1[m-1] > nums2[n-1]:
                nums1[last] = nums1[m-1]
                m -= 1
            else:
                nums1[last] = nums2[n-1]
                n -= 1
            last -= 1
        
        # if nums2 still have remainder
        while n > 0:
            nums1[last] = nums2[n-1]
            last -= 1
            n -= 1

Pattern #4: Split then use 2 pointer to merge

86. Partition List

def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        left, right = ListNode(), ListNode()
        # 2 pointers pointing to last node of each linkedlist
        ltail, rtail = left, right

        # split
        while head:
            if head.val < x:
                ltail.next = head
                ltail = ltail.next
            else:
                rtail.next = head
                rtail = rtail.next
            head = head.next
        
        # merge
        ltail.next = right.next
        rtail.next = None

        return left.next

2. Read this AMAZING article by chuka231.