Two Pointers

#twopointers

Problems

# Problem Difficulty Hint Tags
125 Valid Palindrome - LeetCode Easy
HintWhat makes a palindrome? Move the pointers based on if the characters are matching, or its not a alphanumeric.
#twopointers #string
167 Two Sum II - Input Array Is Sorted - LeetCode Medium
HintHow does the sum of the current pointers relate to moving the pointers?
#array #twopointers #binarysearch
15 3Sum - LeetCode Medium
HintDoes sorting the array make this problem any easier? How can we move pointers based on total sum? What do we do about duplicates?
 #array #twopointers #sorting
11 Container With Most Water - LeetCode Medium
HintWhats the formula for calculating the area? How do we move the pointers based on height?
 #array #twopointers #greedy
42 Trapping Rain Water - LeetCode Red
HintWhat is the formula for calculating rain water?Using two pointers, how can we use the difference between the left and the right pointers to calculate the water? How do we move the pointers?
 #array #twopointers #dynamicprogramming #stack #monotonicstack

Pattern

The two pointer pattern consists of having two different pointers at different parts of an array or a string. Through each pass, we check a condition based on the problem and move the pointers based on this condition.

To recognize its a two pointer problem, it usually involves when you need to find a pair of something (or more) that meets a certain criteria while searching through an array.

The main steps are:

  1. What pointers do I need and where do I start them?
  2. On what condition do I move the pointers?
  3. On what condition do I return the answer?

Tips for strings

Checking if a character is alphabetic (only consists of characters from a-z)

txt = "string"
txt.isalpha() # returns a boolean

Checking if a character is alphanumeric (consists of characters from a-z and 0-9)

txt = "string"
txt.alnum() # returns a boolean