Review: TwoPointers Problems

---

Two pointers problems

---

Basic Abstractions

Name	Summary
two pointers - left/right
two pointers - left/right

Scenarios Code Skeleton Questions

Name	Example

Key Points:

• Time complexity evaluation: pointers back and forth? Minimum Size Subarray Sum
• One loop or two loop?
• “left<right” or “left<=right”? Strobogrammatic Number

## Blog link: https://code.dennyzhang.com/strobogrammatic-number
maps = [('0', '0'), ('1', '1'), ('8', '8'), ('6', '9'), ('9', '6')]
left, right = 0, len(num)-1
while left<=right:
    if (num[left], num[right]) not in maps: return False
    left, right = left+1, right-1
return True

• Use range to change pointer, instead of manual ways. Minimum Window Substring

## Blog link: https://code.dennyzhang.com/minimum-window-substring
left, right = 0, 0
for right in range(0, len1):
    m1[s[right]] += 1
    if self.isTooSmall(m1, m2): continue
    # find a match, then check whether window too big
    while m1[s[left]] > m2[s[left]]:
        m1[s[left]] -= 1
        left += 1
    # find a candidate
    if min_len > right-left+1:
        min_len, res = right-left+1, s[left:right+1]
return res

Sliding window:

• Whether left and right are included?

---

• CheatSheet: Leetcode For Code Interview

See all twopointer problems: #twopointer [display-posts tag=”twopointer” posts_per_page=”100” orderby=”title”]

See more blog_posts.

https://github.com/imhuay/Algorithm_Interview_Notes-Chinese/blob/master/C-算法/专题-B-双指针.md