Fast Slow Pointers¶
Table of Contents¶
- 27. Remove Element (Easy)
- 26. Remove Duplicates from Sorted Array (Easy)
- 80. Remove Duplicates from Sorted Array II (Medium)
- 283. Move Zeroes (Easy)
- 1089. Duplicate Zeros (Easy)
- 287. Find the Duplicate Number (Medium)
27. Remove Element¶
"""
- Remove all instances of a given value in-place.
"""
from typing import List
# Fast Slow Pointers
def removeElement(nums: List[int], val: int) -> int:
fast, slow = 0, 0
while fast < len(nums):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
nums = [0, 1, 2, 2, 3, 0, 4, 2]
val = 2
print(removeElement(nums, val)) # 5
#include <iostream>
#include <vector>
using namespace std;
// Fast Slow Pointers
int removeElement(vector<int>& nums, int val) {
size_t n = nums.size();
size_t slow = 0, fast = 0;
while (fast < n) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return (int)slow;
}
int main() {
vector<int> nums = {3, 2, 2, 3};
int val = 3;
cout << removeElement(nums, val) << endl; // 2
return 0;
}
26. Remove Duplicates from Sorted Array¶
80. Remove Duplicates from Sorted Array II¶
"""
- Allow at most two duplicates.
- fast pointer: explore the array
- slow pointer: point to the position to be replaced
"""
from typing import List
def removeDuplicates(nums: List[int]) -> int:
if len(nums) <= 2:
return len(nums)
fast, slow = 2, 2
while fast < len(nums):
if nums[fast] != nums[slow - 2]:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
nums = [1, 1, 1, 2, 2, 3]
print(removeDuplicates(nums))
283. Move Zeroes¶
"""
- Move all zeroes to the end of the array while maintaining the relative order of the non-zero elements.
"""
from typing import List
def moveZeroes(nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
fast, slow = 0, 0
while fast < len(nums):
if nums[fast] != 0:
nums[slow], nums[fast] = nums[fast], nums[slow]
slow += 1
fast += 1
nums = [0, 1, 0, 3, 12]
moveZeroes(nums)
print(nums) # [1, 3, 12, 0, 0]
#include <iostream>
#include <vector>
using namespace std;
void moveZeroes(vector<int>& nums) {
size_t n = nums.size();
size_t fast = 0, slow = 0;
while (fast < n) {
if (nums[fast] != 0) {
swap(nums[slow], nums[fast]);
slow++;
}
fast++;
}
}
int main() {
vector<int> nums = {0, 1, 0, 3, 12};
moveZeroes(nums);
// [1, 3, 12, 0, 0]
for (size_t i = 0; i < nums.size(); i++) {
cout << nums[i] << " ";
}
cout << endl;
return 0;
}
1089. Duplicate Zeros¶
"""
- Duplicate each occurrence of zero, shifting the remaining elements to the right.
"""
from typing import List
def duplicateZeros(arr: List[int]) -> None:
"""
Do not return anything, modify arr in-place instead.
"""
n = len(arr)
fast, slow = 0, 0
# First pass: find the position
# where the last element would be in the expanded array
while fast < n:
if arr[slow] == 0:
fast += 1
slow += 1
fast += 1
slow -= 1
fast -= 1
# Second pass: move elements backwards
while slow >= 0:
if fast < n:
arr[fast] = arr[slow]
if arr[slow] == 0:
fast -= 1
if fast < n:
arr[fast] = 0
slow -= 1
fast -= 1
arr = [1, 0, 2, 3, 0, 4, 5, 0]
duplicateZeros(arr)
print(arr) # [1, 0, 0, 2, 3, 0, 0, 4]
287. Find the Duplicate Number¶
"""
- Find the duplicate number in an array containing `n + 1` integers where each integer is between `1` and `n` inclusive.
- Floyd's Tortoise and Hare (Cycle Detection)
- 141. Linked List Cycle
- 142. Linked List Cycle II
- Time Complexity: O(n)
- Space Complexity: O(1)
Example: `nums = [1, 3, 4, 2, 2]`
| 0 | 1 | 2 | 3 | 4 |
| :--: | :--: | :--: | :--: | :--: |
| 1 | 3 | 4 | 2 | 2 |
"""
from typing import List
# Floyd Cycle Detection Algorithm
def findDuplicate(nums: List[int]) -> int:
fast, slow = nums[0], nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
nums = [1, 3, 4, 2, 2]
print(findDuplicate(nums)) # 2