Two Pointers: Inward Traversal

A pointer is a variable that represents and index or position within a data structure, such as an Array or Linked List. With Two pointers we can make comparisons, with a pointer at two different positions, and infer a decision based on that. 

When to use:

• Data Structure: Linear such as Array, Linked List
• Predictable Dynamics such as Sorted Array or Palindrome
• Result asks for Pair of Values
• One Result is decided by a Pair of Values

Brute Force:

• Checking All Possible Pairs using Nested Loop
  • Outer Loop traverses the array for the first element of the pair
  • Inner Loop traverses the rest of the array to find second element 
• Time Complexity is O(n^2) where n is length of the loop ( Two Loops )
• Does not take account predictable dynamics (sorted) 

Real-World Example:

Garbage Collection Algorithm 

def pair_sum_sorted(nums: List[int], target: int) -> List[int]:
  left, right = 0, len(nums)-1
  while left < right:
    sums = nums[left] + nums[right]
    # if the sum is smaller, increment the left pointer, aiming 
    # to increase the sum towards the target value
    if sums < target:
      left += 1
    # if the sum is larger, decrement the right pointer, aiming 
    # to decrease the sum towards the target value
    elif sums > target:
      right -=1
    # If target pair is found return its indices 
    else: 
      return [left,right]
  return []