Two Pointers Flashcards
(19 cards)
What types of data structures can the two pointers pattern be applied to?
Sequential data structures such as arrays or linked lists.
What is a key advantage of using the two pointers pattern?
It allows for efficient exploration of data with optimal time and space complexity.
In the context of strings, how can the two pointers pattern be used to check for palindromes?
One pointer iterates from the beginning and the other from the end, comparing values at each step.
What is the time complexity of the naive approach to solving problems compared to the two pointers approach?
The naive approach has a time complexity of O(n²) while the two pointers approach can achieve O(n).
What is an example of a problem that can be solved using the two pointers pattern?
- Reversing an array in place.,
- pallindrome ,
- Pair with given sum in a sorted array
True or False: The two pointers pattern can be used for memory management.
True.
In memory management, what do the start and end pointers represent?
The start pointer points to the beginning of the available memory block, and the end pointer indicates the end of the block.
What type of problems can the two pointers pattern typically address?
Problems that fulfill the following conditions:
* Linear data structure
* Process pairs
* Dynamic pointer movement.
Match the problem: Given an array of integers, move all zeros to the end of the array.
Two Pointers.
Match the problem: Generate a string of n balanced parentheses.
Some other pattern.
Match the problem: Find any three values in a sorted array that sum up to 825.
Two Pointers.
Match the problem: Find all permutations of the following set of elements: {1, 2, 3}.
Some other pattern.
Reversing an array: Given an array of integers, reverse it in place
Pair with given sum in a sorted array: Given a sorted array of integers, find a pair in the array that sums to a number T
Valid palindrome logic
Solution summary#
Initialize two pointers: one at the beginning (left) and one at the end (right) of the string.
Move both pointers toward the center, skipping any characters that are not alphanumeric.
At each step, compare the characters at the left and right positions after converting them to lowercase.
If a mismatch is found, return False, indicating that the string is not a palindrome.
If the entire string is traversed without mismatches, return True, indicating that the string is a valid palindrome.
Time complexity
The time complexity of the above solution is
O(n)
Space complexity
The space complexity of the above solution is
O(1)
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
def main():
test_cases = [
("A man, a plan, a canal: Panama"),
("race a car"),
("1A@2!3 23!2@a1"),
("No 'x' in Nixon"),
("12321"),
]
for i in test_cases:
print("\tstring: ", i)
result = is_palindrome(i)
print("\n\tResult:", result)
print("-"*100)
if __name__ == “__main__”:
main()
.
3 SUM problem
The essence of the solution lies in first sorting the array, which makes it easier to find positive numbers that balance out negative ones to sum to zero, and also helps in skipping duplicates. Then, for each number in the array, we search for two other numbers to the right that, together with it, sum to zero. This is done using two pointers—low and high—starting just after the fixed number and at the end of the array, respectively. We calculate the sum of each triplet as nums[i] + nums[low] + nums[high]. If the total is less than zero, we move the low pointer forward to increase the sum; if it’s greater than zero, we move the high pointer backward to decrease the sum. When the sum is exactly zero, we add the triplet to the result and move both pointers inward, skipping duplicates to ensure all triplets are unique.
Using the intuition above, we implement the algorithm as follows:
Sort the input array nums in ascending order to make it easier to find triplets and skip duplicates.
Create an empty array, result, to store the unique triplets.
Store the length of nums in a variable n.
Iterate over the array from index i = 0 to n - 2 (as we are looking for triplets).
Break the loop if the current number nums[i] is greater than 0. As the array is sorted, all remaining numbers will be positive, and any triplet including nums[i] will have a sum greater than zero.
If i == 0 or nums[i] is not equal to nums[i - 1], this ensures that the current number is either the first element or not a duplicate of the previous element.
Initialize two pointers: low = i + 1 and high = n - 1.
Run a loop as long as low is less than high.
Calculate the sum: nums[i] + nums[low] + nums[high].
If the sum is less than 0, move the low pointer forward to increase the sum.
If the sum is greater than 0, move the high pointer backward to decrease the sum.
Otherwise, add [nums[i], nums[low], nums[high]] to the result, as this triplet sums to 0.
Move low and high to the next distinct values to avoid duplicate triplets. This is done by incrementing low while nums[low] == nums[low - 1], and decrementing high while nums[high] == nums[high + 1].
After iterating through the whole array, return the result that contains all unique triplets that sum to zero.
def three_sum(nums):
# Sort the input array in ascending order
nums.sort()
# Create an empty array to store the unique triplets
result = []
# Store the length of the array in a variable
n = len(nums)
# Iterate over the array till n - 2
for i in range(n - 2):
# If the current number is greater than 0, break the loop
if nums[i] > 0:
break
# The current number is either the first element or not a duplicate of the previous element
if i == 0 or nums[i] != nums[i - 1]:
# Initialize two pointers
low, high = i + 1, n - 1
# Run a loop as long as low is less than high
while low < high:
# Calculate the sum of the triplet
sum = nums[i] + nums[low] + nums[high]
# If the sum is less than 0, move the low pointer forward
if sum < 0:
low += 1
# If the sum is greater than 0, move the high pointer backward
elif sum > 0:
high -= 1
else:
# Add the triplet to result as this triplet sums to 0
result.append([nums[i], nums[low], nums[high]])
# Move both pointers to the next distinct values to avoid duplicate triplets
low += 1
high -= 1
while low < high and nums[low] == nums[low - 1]:
low += 1
while low < high and nums[high] == nums[high + 1]:
high -= 1
# Return result, which contains all unique triplets that sum to zero
return result
Driver code
def main():
nums_arrs = [
[-1, 0, 1, 2, -1, -4],
[1, 2, 3, 4, 5],
[0, 0, 0, 0],
[-4, -1, -1, 0, 1, 2, 2],
[-10, -7, -3, -1, 0, 3, 7, 10],
[-3, -5, -7, -9]
]
for i, nums in enumerate(nums_arrs):
print(f"{i + 1}.\tnums: [{', '.join(map(str, nums))}]\n")
print(f"\tTriplets: {three_sum(nums)}")
print('-' * 100)
if __name__ == “__main__”:
main()
3 SUM time complexity and space complexity
Given the head of a singly linked list and an integer n, remove the nth node from the end of the list and return the head of the modified list.
def remove_nth_last_node(head, n):
# Point two pointers, right and left, at head.
right = head
left = head
# Move right pointer n elements away from the left pointer.
for i in range(n):
right = right.next
# Removal of the head node.
if not right:
return head.next
# Move both pointers until right pointer reaches the last node.
while right.next:
right = right.next
left = left.next
# At this point, left pointer points to (n-1)th element.
# So link it to next to next element of left.
left.next = left.next.next
return head
Driver code
def main():
lists = [[23, 89, 10, 5, 67, 39, 70, 28], [34, 53, 6, 95, 38, 28, 17, 63, 16, 76], [288, 224, 275, 390, 4, 383, 330, 60, 193],
[1, 2, 3, 4, 5, 6, 7, 8, 9], [69, 8, 49, 106, 116, 112, 104, 129, 39, 14, 27, 12]]
n = [4, 1, 6, 9, 11]
for i in range(len(n)):
input_linked_list = LinkedList()
input_linked_list.create_linked_list(lists[i])
print(i+1, ". Linked List:\t", end='')
print_list_with_forward_arrow(input_linked_list.head)
print()
print("n = ", n[i])
result = remove_nth_last_node(input_linked_list.head, n[i])
print("Updated Linked List:\t", end='')
print_list_with_forward_arrow(result)
print()
print("-"*100)
if __name__ == ‘__main__’:
main()
Solution summary and Time and Space complexity for: Given the head of a singly linked list and an integer n, remove the nth node from the end of the list and return the head of the modified list
