Review: TwoPointers Problems Posted on January 18, 2018September 3, 2019 by braindenny 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? See all twopointer problems: #twopointer Review: TwoPointers ProblemsLintCode: Reverse ArrayLintCode: Delete CharactersLintCode: 3Sum IILeetCode: Valid Triangle NumberLeetcode: Valid PalindromeLeetCode: Two Sum IV – Input is a BSTLeetCode: Two Sum II – Input array is sortedLeetCode: Two SumLeetCode: Sum of Square NumbersLeetcode: Subarray Product Less Than KLeetcode: Squares of a Sorted ArrayLeetCode: Sort ColorsLeetcode: Sort Array By ParityLeetcode: Reverse Only LettersLeetcode: Replace the Substring for Balanced StringLeetcode: Remove Nth Node From End of ListLeetcode: Random Pick with BlacklistLeetCode: Partition LabelsLeetcode: Minimum Size Subarray SumLeetcode: Merge Sorted ArrayLeetcode: Meeting SchedulerLeetcode: Longest Chunked Palindrome DecompositionLeetcode: Long Pressed NameLeetcode: Last Substring in Lexicographical OrderLeetcode: K-diff Pairs in an ArrayLeetcode: Fruit Into BasketsLeetcode: Duplicate ZerosLeetcode: DI String MatchLeetcode: Count Binary SubstringsLeetcode: Container With Most WaterLeetCode: Check If a String Can Break Another StringLeetcode: Bag of TokensLeetcode: Assign CookiesLeetCode: 4SumLeetCode: 3Sum SmallerLeetCode: 3Sum ClosestLeetCode: 3Sum See more blog_posts. Post Views: 9