Array with Two Pointers
Fast and Slow Pointers
Remove Duplicates from Sorted Array (Leetcode 26)
Here an important thing is that if we have a sorted array, we can use two pointers to solve the problem in O(n) space complexity. Otherwise, if we remove each duplicate element, we need to shift the elements to the left, which will take O(n^2) time complexity.
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
slow = 0
fast = 0
while fast < len(nums)-1:
fast += 1
if nums[slow] != nums[fast]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
This is similar to Leetcode 83.
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return head
slow, fast = head, head
while True:
fast = fast.next
if fast is None:
break
if slow.val != fast.val:
slow.next = fast
slow = slow.next
slow.next = None
return head
Remove Element (Leetcode 27)
Here we can use two pointers to solve the problem in O(n) time complexity.
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
slow, fast = 0, 0
while fast < len(nums):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
fast += 1
return slow
Move Zeroes (Leetcode 283)
This is similar to removing elements from an array.
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
slow, fast = 0, 0
while fast < len(nums):
if nums[fast] != 0:
nums[slow] = nums[fast]
slow += 1
fast += 1
for i in range(slow, fast):
nums[i] = 0
return nums
Sliding Window
The sliding window is a technique that is useful when we need to find a subarray or substring that satisfies a certain condition. The key idea is to use two pointers to maintain the window and update the window based on the condition.
int left = 0, right = 0;
while right < len(nums):
# expand the window
window.addLast(nums[right])
right += 1
while (window needs shrink):
# shrink the window
window.removeFirst(nums[left])
left += 1
Minimum Window Substring (Leetcode 76)
NOTE: An important thing of this problem is that we need to update the win_temp[char] even it might exceed the temp[char]. This is because we need to keep track of the number of characters that are matched as there might be duplicates in the template.
class Solution:
def minWindow(self, s: str, t: str) -> str:
start = 0
end = 0
min_length = float('inf')
# Form the template and num_str needs to be matched
temp = {}
win_temp = {}
num_str = len(t)
for char in t:
temp[char] = temp.get(char, 0) + 1
while end < len(s):
char = s[end]
win_temp[char] = win_temp.get(char, 0) + 1
if char in temp and win_temp[char] <= temp[char]:
num_str -= 1
while num_str == 0:
if s[start] in temp:
# record min_length
if end - start + 1 < min_length:
start_index = start
min_length = end - start + 1
win_temp[s[start]] -= 1
if win_temp[s[start]] < temp[s[start]]:
num_str += 1
start += 1
end += 1
return "" if min_length == float('inf') else s[start_index:start_index + min_length]
Permutation in String (Leetcode 567)
class Solution:
def checkInclusion(self, s1: str, s2: str) -> bool:
start = 0
end = 0
num_elements = len(s1)
temp_s1 = {}
temp_window = {}
for char in s1:
temp_s1[char] = temp_s1.get(char, 0) + 1
while end < len(s2):
char = s2[end]
temp_window[char] = temp_window.get(char, 0) + 1
if char in temp_s1 and temp_window[char] <= temp_s1[char]:
num_elements -= 1
if end - start + 1 > len(s1):
start_char = s2[start]
temp_window[start_char] -= 1
if start_char in temp_s1 and temp_window[start_char] < temp_s1[start_char]:
num_elements += 1
start += 1
if num_elements == 0:
return True
end += 1
return False
Left and Right Pointers
Two Sum (Leetcode 167)
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:
sum_lr = numbers[left] + numbers[right]
if sum_lr < target:
left += 1
elif sum_lr > target:
right -= 1
else:
return [left + 1, right + 1]
return [-1, 1]
Reverse String (Leetcode 344)
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
left, right = 0, len(s) - 1
while left < right:
temp = s[left]
s[left] = s[right]
s[right] = temp
left += 1
right -= 1
return s
Longest Palindromic Substring (Leetcode 5)
class Solution:
def palindrome(self, s:str, l1:int, l2:int):
while l1 >= 0 and l2 <len(s) and s[l1] == s[l2]:
l1 -= 1
l2 += 1
return s[l1+1:l2]
def longestPalindrome(self, s: str) -> str:
res = ''
for i in range(len(s)):
res1 = self.palindrome(s, i, i)
res2 = self.palindrome(s, i, i+1)
if len(res1) > len(res):
res = res1
if len(res2) > len(res):
res = res2
return res