LeetCode Two Pointers related problems

before I wrote this article, I just think that two pointer technique is nothing like iteration, but in an efficient way. it’s like brute force with memo.

sometimes, I mean, many times, I just implement those things straightly, and after that I found that those corner case are too frustrate to solve. like 487 567. think about this, it is a general problem along with all your coding and debug phrase.

003 longest substring without repeating characters, this problem is kind of interesting, it can be done in explicit two pointers, or use hashmap, or just use queue. take a look at your previous submission, it is quite interesting.

011 container with most water: this is a really classic one. use double direction pointers. the general idea is pretty simple: bucket theory. we want to make an improvement for this bucket, so we want to improv the short one, that is the only way the possible can improve the maximum of water contained.

017 two sum3-data structure design: originally, we solved this problem by hashmap, but it actually can be done using 2 pointers. this problem is really easy actually. just pay attention to details.

015 three sum: we have to do some kind of presort. and we will use three pointers

016 three sum closest: the same with LC15, and we will maintain a value to record the closest.

018 4sum. still classic

019 remove Nth node from the end of the list: linkedlist related problem, I believe we have no choice but to use pointers.

026 remove duplicate from sorted array: remove the duplicates in place. just rewrite them,like selection sort. we need two pointers, one use to iterate original array and the other uses to construct new array

027 remove element: like LC26 same here

028 implement indexOf(String substring): it is like string match, we have KMP or Rabin Karp or Boyers and other matching algorithm. and of course, using two pointers will also be very easy.

030 substring with concatenation of all words: this problem is kind of hard to solve, this problem is quite like LC28, but like an advanced version. this is a not very hard problem even though it says hard. the implement is pretty straight forward.

042 Trapping rain water: another tapping water related problem. last problem is the bucket without thickness, but this problem the number of waters it can contains. and this time we still using double direction pointers. but we maintained two other variables, leftMax and rightMax

061 rotate list: rotate a linkedlist: we met this kind of problems, but it just needs us to rotate an array. but for this problem, we have a genius way like make it a loop and relocate head and unleash the loop. we may say this problem is not two pointer related problem. but does any linkedlist problem not be solved in pointer?

075 Sort colors: sort an array which only contains three colors. do the sort in place: we did know we need to swap sth to do it inplace. it is pretty tricky, so think carefully

076 minimum window substring: given two strings, find the minimum length of substring in s which contains all the characters in T in linear time. this problem is hard, , i means, these kind of two pointer problem can easily be solved in brute force, but this time, we have to do it in O(n)

080 remove duplicate form sorted array2: remove in place and all items needs to less than or equals to twice. it seems simple, but just thinking clearly. not hash.

086 Partition List: linkedlist related problems. very simple

088 merge sorted array: still a simple 2 pointers problem, pretty genius way to do it, just think reversely.

125 valid palindrome: check if a given string is palindrome, ignore cases and other chars. this problem is so simple! just use two direction pointers, and use the Character.toLowerCase() and Character.isLetterOrDgits()

141 linked list cycle: check if linkedlist has cycle

142 linkedlist cycle2: return the start node of cycle

159 longest substring with at most two distinct characters: this can be done in simulate hash map and two pointers. we have to template for this kind of problems.

167 2 sum 2-input array is sorted: double direction pointers, very simple

209 minimum size sub array sum: find the minimum length of subarray(contiguous) such that the sum of it is >= s. this problem can also use template in LC159 to solve this problem.

234 palindrome linkedlist: reverse right part, and use two pointers to compare. very simple

259 3 sum smaller: calculate the number of triplets that smaller than target. the same as 3 sum . just use presort and two pointers, O(n^2). or we don’t use two pointers technique, instead, we presort it, and use nested binary search to search the target we want each time.

283 move zeros: move all element that is 0 to tail of the array, do it in place. and remain the relative order of non-0 elements. classic overwrite problem, just remember to rewrite [j, m] with 0;

287 find the duplicate number: the array is read-only and rum time need to less than O(n^2), O(1) space. there is some very important statement:the array contains n+1 integers which each integer is between [1~n]. for this problem we have many methods like presort, or hashset, and we can even do it in mathematical way.

344 reverse string: two pointer keeps swapping

345 reverse vowels of a string: it is a very simple question! but just could figure it out what the problem is!!! ???

349 intersection of two arrays: still a very simple question, but takes many time to implement.because array, arraylist and hashset are too hard(?) to covert with each other

350 intersection of two arrays2: simple problem.

360 sort transformed array: two pointers, but this time, based on the relative value of function(i) and function(j) we move different pointer each time.

424: longest repeating character replacement: the general idea is pretty simple, but have so many details to care about.

487 max consecutive ones2:

567: permutation in string: this is a simple problem, but the corner case is too frustrated to solve.