Review: TwoPointers Problems

Posted on January 18, 2018July 26, 2020 by braindenny

Two pointers problems

Basic Abstractions

Name	Summary
two pointers – left/right
two pointers – left/right

Scenarios
Code Skeleton
Top 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?

See all twopointer problems: #twopointer

See more blog posts.

Post Views: 9