2pointer-article -leetcode.pdf

Hello, I have been solving all two pointers tagged problems in last 3.5 months, and wanted to share my findings/classifications here. If you are preparing for technical interview, two pointers is one of the popular topics that you can't skip :). There are around 140 problems today, but I only solved...

Hello, I have been solving all two pointers tagged problems in last 3.5 months, and wanted to share my findings/classifications here. If you are preparing for technical interview, two pointers is one of the popular topics that you can't skip :). There are around 140 problems today, but I only solved the public ones (117 problems). Majority of them is in easy or medium so, if you understand the basic ideas then it should be solvable without much hints and editorials. I see 4 bigger categories and many sub categories in it, and marked the typical example problems with (*). I would recommend you to start solving these example problems, and apply the knowledge to the other problems. I don't want to copy & paste my ugly codes here, you would easily find fantastic solutions from the problem discussion page. 1. Running from both ends of an array The first type of problems are, having two pointers at left and right end of array, then moving them to the center while processing something with them. 2 Sum problem (*) https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/ https://leetcode.com/problems/3sum/ https://leetcode.com/problems/4sum/ https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given- sum-condition/ https://leetcode.com/problems/two-sum-iv-input-is-a-bst/ https://leetcode.com/problems/sum-of-square-numbers/ https://leetcode.com/problems/boats-to-save-people/ https://leetcode.com/problems/minimize-maximum-pair-sum-in-array/ https://leetcode.com/problems/3sum-with-multiplicity/  Trapping Water (*) https://leetcode.com/problems/trapping-rain-water/ https://leetcode.com/problems/container-with-most-water/ Next Permutation (*) https://leetcode.com/problems/next-permutation/ https://leetcode.com/problems/next-greater-element-iii/ https://leetcode.com/problems/minimum-adjacent-swaps-to-reach-the-kth- smallest-number/ Reversing / Swapping https://leetcode.com/problems/valid-palindrome/ (*) https://leetcode.com/problems/reverse-string/ https://leetcode.com/problems/reverse-vowels-of-a-string/ https://leetcode.com/problems/valid-palindrome-ii/ https://leetcode.com/problems/reverse-only-letters/ https://leetcode.com/problems/remove-element/ https://leetcode.com/problems/sort-colors/ https://leetcode.com/problems/flipping-an-image/ https://leetcode.com/problems/squares-of-a-sorted-array/ https://leetcode.com/problems/sort-array-by-parity/ https://leetcode.com/problems/sort-array-by-parity-ii/ https://leetcode.com/problems/pancake-sorting/ https://leetcode.com/problems/reverse-prefix-of-word/ https://leetcode.com/problems/reverse-string-ii/ https://leetcode.com/problems/reverse-words-in-a-string/ https://leetcode.com/problems/reverse-words-in-a-string-iii/ Others https://leetcode.com/problems/bag-of-tokens/ https://leetcode.com/problems/di-string-match/ https://leetcode.com/problems/minimum-length-of-string-after-deleting-similar- ends/ https://leetcode.com/problems/sentence-similarity-iii/ https://leetcode.com/problems/find-k-closest-elements/ https://leetcode.com/problems/shortest-distance-to-a-character/  2.Slow & Fast Pointers Next type is using two pointers with diYerent speed of movement. Typically they starts from the left end, then the first pointer advances fast and give some feedback to the slow pointer and do some calculation. Linked List Operations (*) https://leetcode.com/problems/linked-list-cycle/ https://leetcode.com/problems/linked-list-cycle-ii/ https://leetcode.com/problems/remove-nth-node-from-end-of-list/ https://leetcode.com/problems/rotate-list/ https://leetcode.com/problems/reorder-list/ https://leetcode.com/problems/palindrome-linked-list/ Cyclic Detection (*) https://leetcode.com/problems/find-the-duplicate-number/ https://leetcode.com/problems/circular-array-loop/ Sliding Window/Caterpillar Method (*) https://leetcode.com/problems/number-of-subarrays-with-bounded-maximum/ https://leetcode.com/problems/find-k-th-smallest-pair-distance/ https://leetcode.com/problems/moving-stones-until-consecutive-ii/ https://leetcode.com/problems/count-pairs-of-nodes/ https://leetcode.com/problems/count-binary-substrings/ https://leetcode.com/problems/k-diY-pairs-in-an-array/  Rotation (*) https://leetcode.com/problems/rotating-the-box/ https://leetcode.com/problems/rotate-array/ String (*) https://leetcode.com/problems/string-compression/ https://leetcode.com/problems/last-substring-in-lexicographical-order/ Remove Duplicate (*) https://leetcode.com/problems/remove-duplicates-from-sorted-array/ https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/ https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/ https://leetcode.com/problems/duplicate-zeros/ Others https://leetcode.com/problems/statistics-from-a-large-sample/ https://leetcode.com/problems/partition-labels/ https://leetcode.com/problems/magical-string/ https://leetcode.com/problems/friends-of-appropriate-ages/ https://leetcode.com/problems/longest-mountain-in-array/ https://leetcode.com/problems/shortest-subarray-to-be-removed-to-make-array- sorted/  3.Running from beginning of 2 arrays / Merging 2 arrays In this category, you will be given 2 arrays or lists, then have to process them with individual pointers. Sorted arrays (*) https://leetcode.com/problems/merge-sorted-array/ https://leetcode.com/problems/heaters/ https://leetcode.com/problems/find-the-distance-value-between-two-arrays/ Intersections/LCA like (*) https://leetcode.com/problems/intersection-of-two-linked-lists/ https://leetcode.com/problems/intersection-of-two-arrays/ https://leetcode.com/problems/intersection-of-two-arrays-ii/ SubString (*) https://leetcode.com/problems/implement-strstr/ https://leetcode.com/problems/longest-word-in-dictionary-through-deleting/ https://leetcode.com/problems/long-pressed-name/ https://leetcode.com/problems/longest-uncommon-subsequence-ii/ https://leetcode.com/problems/compare-version-numbers/ https://leetcode.com/problems/camelcase-matching/ https://leetcode.com/problems/expressive-words/ Median Finder (*) https://leetcode.com/problems/find-median-from-data-stream/  Meet-in-the-middle / Binary Search (*) https://leetcode.com/problems/partition-array-into-two-arrays-to-minimize- sum-diYerence/ https://leetcode.com/problems/closest-subsequence-sum/ https://leetcode.com/problems/ways-to-split-array-into-three-subarrays/ https://leetcode.com/problems/3sum-closest/ https://leetcode.com/problems/valid-triangle-number/ Others https://leetcode.com/problems/shortest-unsorted-continuous-subarray/ https://leetcode.com/problems/most-profit-assigning-work/ https://leetcode.com/problems/largest-merge-of-two-strings/ https://leetcode.com/problems/swap-adjacent-in-lr-string/ 4.Split & Merge of an array / Divide & Conquer The last one is similiar to previous category but there is one thing is added. First, you need to split the given list into 2 separate lists and then do two pointers approach to merge or unify them. There aren't many tasks here. Partition (*) https://leetcode.com/problems/partition-list/  Sorting (*) https://leetcode.com/problems/sort-list/