Two Pointers
Types of questions
Remove duplicates
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
slow = 0
fast = 1
while fast < len(nums):
if nums[fast] != nums[slow]:
slow += 1
# 维护 nums[0..slow] 无重复
nums[slow] = nums[fast]
fast += 1
# 数组长度为索引 + 1
return slow + 1
| Method | Related Questions |
|---|---|
| From both ends of the array | 167. Two Sum II - Input Array Is Sorted, 31. Next Permutation |
| Slow & Fast pointers - replace slow with fast if condition holds |
287. Find the Duplicate Number, 795. Number of Subarrays with Bounded Maximum, 209. Minimum Size Subarray Sum |
| Running from beginning of 2 arrays / Merging 2 arrays | |
| Split & Merge of an array / Divide & Conquer | |
259. 3Sum Smaller
1055. Shortest Way to Form String
| File | confidence | date | difficulty | note |
|---|---|---|---|---|
| 1268. Search Suggestions System | 🟡 | May 10, 2024 | medium | Sort the array, use two pointer to shrink the search range |
| 80. Remove Duplicates from Sorted Array II | 🟡 | May 31, 2024 | medium | Fast slow pointers, with a additional counter variable, compare fast with the previous element |
| 259. 3Sum Smaller | 🔴 | September 02, 2024 | medium | Anchor the first, then do two pointer on the remaining |
| 1055. Shortest Way to Form String | 🔴 | September 07, 2024 | medium | One pointer at target, one at the source, loop source multiples times to match the target greedily |
| 277. Find the Celebrity | 🔴 | September 11, 2024 | medium | Find the potential celebrity, then verify it |
| 75. Sort Colors | 🔴 | September 26, 2024 | medium | Two pointer plus a fast-slow pointer |
| 42. Trapping Rain Water | 🟡 | September 26, 2024 | hard | To evaluate water a index l, it relies on the l_max variable, and l_max would always smaller or equal to r_max since we are moving the pointer to follow such logic |
| 786. K-th Smallest Prime Fraction | 🔴 | October 12, 2024 | medium | Binary search from interval 0 to 1 |
| 481. Magical String | 🔴 | December 05, 2024 | medium | Input the first two cluster, the insert chunk by chunk |
| 408. Valid Word Abbreviation | 🔴 | December 13, 2024 | easy | - |
| File | confidence | date | difficulty | note |
|---|---|---|---|---|
| 11. Container With Most Water | 🟢 | March 07, 2024 | - | - |
| 76. Minimum Window Substring | 🟢 | March 08, 2024 | hard | - |
| 3. Longest Substring Without Repeating Characters | 🟢 | March 17, 2024 | - | - |
| 15. 3 Sum | 🟢 | June 08, 2024 | medium | check left and right pointer when removing the duplicates |
| 633. Sum of Square Numbers | 🟢 | July 07, 2024 | medium | The domain is restricted to c, then use two pointers |