Slow&FastPointers Flashcards
(20 cards)
What is the main purpose of the Fast and Slow Pointers pattern?
To traverse an iterable data structure at different speeds to identify cycles or find a specific target.
What are the speeds of the slow and fast pointers in the Fast and Slow Pointers pattern?
The slow pointer moves one step at a time, while the fast pointer moves two steps at a time.
In the Fast and Slow Pointers method, what happens if a cycle exists in the data structure?
The two pointers will eventually meet during traversal.
What is the first condition that must be fulfilled for a problem to match the Fast and Slow Pointers pattern?
The input data can be traversed in a linear fashion.
What types of data structures can be traversed using the Fast and Slow Pointers pattern?
- Array
- Linked list
- String
What is the second condition that may be required for using the Fast and Slow Pointers pattern?
The problem involves detecting a loop or finding an intersection.
What is a real-world example of using the Fast and Slow Pointers pattern for symlink verification?
Detecting loops where symlinks endlessly reference each other.
During compilation, how can the Fast and Slow Pointers pattern help with object-oriented modules?
It helps track dependencies step by step to identify cyclic dependencies.
Fill in the blank: The Fast and Slow Pointers pattern is commonly used to find the _______ of a linked list.
middle node
True or False: The Fast and Slow Pointers pattern can only be used for linked lists.
False
What is a problem that can be solved using the Fast and Slow Pointers pattern?
Detect a cycle in an array.
What is the significance of the condition ‘someCondition’ in the Fast and Slow Pointers pseudocode?
It triggers handleCondition when met.
What is an example of detecting a cycle in an array using Fast and Slow Pointers?
Given an array of indexes pointing to the next element.
What is meant by finding the starting element of the second quantile?
Identifying where the second part of a divided dataset begins.
Happy Number Algorithm
Problem Statement
Determine if a given number n is a “happy number” through a specific digit transformation process.
Algorithm Overview
1. Transform number by summing squares of its digits
2. Repeat transformation until:
- Number becomes 1 (Happy Number)
- Number enters a cycle (Not a Happy Number
Solution Approaches
Approach 1: Hash Set Cycle Detection
python
def getDigitSquareSum(num):
totalSum = 0
while num > 0:
digit = num % 10
totalSum += digit * digit num //= 10
return totalSum
def isHappyNumber(n):
seen = set()
while n != 1 and n not in seen:
seen.add(n)
n = getDigitSquareSum(n)
return n == 1
Approach 2: Floyd’s Cycle Detection
————
def is_happy_number(n):
# Helper function that calculates the sum of squared digits.
def sum_of_squared_digits(number):
total_sum = 0
while number > 0:
number, digit = divmod(number, 10)
total_sum += digit ** 2
return total_sum
slow_pointer = n
fast_pointer = sum_of_squared_digits(n)
while fast_pointer != 1 and slow_pointer != fast_pointer:
slow_pointer = sum_of_squared_digits(slow_pointer)
fast_pointer = sum_of_squared_digits(sum_of_squared_digits(fast_pointer))
if(fast_pointer == 1):
return True
return False
Time and Space Complexity
Approach 1: Hash Set
- Time Complexity: O(log n)
- Space Complexity: O(log n)
Approach 2: Floyd’s Cycle
- Time Complexity: O(log n)
- Space Complexity: O(1)
Key Considerations
- Handle single-digit and multi-digit numbers
- Detect infinite loops
- Efficiently compute digit square sum
Linked List Cycle Detection Algorithm
Problem Statement
Determine if a linked list contains a cycle by detecting if a node can be revisited by continuously following next pointers.
Algorithm Overview
1. Detect if nodes can form a circular reference
2. Return boolean indicating cycle presence
3. Handle various linked list configurations
from linked_list import LinkedList
from print_list import *
def detect_cycle(head):
if head is None:
return False
# Initialize two pointers, slow and fast,
# to the head of the linked list
slow, fast = head, head
# Run the loop until we reach the end of the
# linked list or find a cycle
while fast and fast.next:
# Move the slow pointer one step at a time
slow = slow.next
# Move the fast pointer two steps at a time
fast = fast.next.next
# If there is a cycle, the slow and fast pointers will meet
if slow == fast:
return True
# If we reach the end of the linked list and haven't found a cycle,
# return False
return False
Middle of the Linked List Algorithm
Problem Statement
Find the middle node of a singly linked list.
- For odd-length lists: Return exact middle node
- For even-length lists: Return second middle node
def get_middle_node(head):
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
There is a circular list of non-zero integers called nums. Each number in the list tells you how many steps to move forward or backward from your current position:
If nums[i] is positive, move nums[i] steps forward.
If nums[i] is negative, move nums[i] steps backward.
As the list is circular:
Moving forward from the last element takes you back to the first element.
Moving backward from the first element takes you to the last element.
A cycle in this list means:
You keep moving according to the numbers, and you end up repeating a sequence of indexes.
All numbers in the cycle have the same sign (either all positive or all negative).
The cycle length is greater than 1 (it involves at least two indexes).
Return true if such a cycle exists in the list or false otherwise.
def circular_array_loop(nums):
size = len(nums)
for i in range(size):
slow = fast = i
forward = nums[i] > 0
while True:
slow = next_step(slow, nums[slow], size)
if is_not_cycle(nums, forward, slow):
break
fast = next_step(fast, nums[fast], size)
if is_not_cycle(nums, forward, fast):
break
fast = next_step(fast, nums[fast], size)
if is_not_cycle(nums, forward, fast):
break
if slow == fast:
return True
return False
A function to calculate the next step
def next_step(pointer, value, size):
return (pointer + value) % size
A function to detect a cycle doesn’t exist
def is_not_cycle(nums, prev_direction, pointer):
curr_direction = nums[pointer] >= 0
if (prev_direction != curr_direction) or (nums[pointer] % len(nums) == 0):
return True
else:
return False
Statement: Palindrome Linked List
Given the head of a linked list, your task is to check whether the linked list is a palindrome or not. Return TRUE if the linked list is a palindrome; otherwise, return FALSE.
Solution
Checking whether a sequence is a palindrome typically involves using two pointers—one at the start and the other at the end—comparing elements while moving toward the center. While this approach is intuitive, it is not directly feasible for a singly linked list, as it only has next pointers and lacks previous pointers for backward traversal. To overcome this limitation, we solve the problem in four key steps: find the midpoint of the given linked list using a slow and fast pointer technique. Next, we reverse the second half of the list so that we can compare it directly with the first half. Reversing the second half allows us to bring the last elements to the front, aligning them with the first half for direct comparison using only the next pointers. If the values in both halves match during this step, the linked list is a palindrome. Finally, we reverse the second half again to restore the list to its original order, ensuring the data structure remains unchanged after the check.
The algorithm has the following workflow:
First, we will find the middle node of the linked list. To do this, we’ll traverse the linked list using two pointers, where the slow pointer will move one step forward, and the fast pointer will move two steps forward. We’ll do this until the fast pointer reaches the end of the list or a null node. At this point, the slow pointer will be pointing at the middle node of the list.
Next, we’ll reverse the second_half of the linked list, starting from the node after the middle node. To reverse the list, we will call the function reverseLinkedList, passing the slow node as a parameter, representing the head of the second_half of the linked list. We will follow these steps in the reverseLinkedList function:
Initialize three pointers: prev, next, and curr. The prev and next pointers are initialized as NULL, while curr is initialized to the head of the linked list.
Iterate over the linked list. While iterating, perform the following steps:
Before changing the next of curr, store the next node using the following line of code: next = curr.next.
Now, we will update the next pointer of curr with the prev pointer. This will reverse the pointer of the current node from forward to backward, eventually aiding the reversal of the linked list.
After reversing the pointer, we will update prev as curr and curr as next, using the following lines of code: prev = curr and curr = next.
from LinkedListReversal import reverse_linked_list
def palindrome(head):
# Initialize slow and fast pointers to the head of the linked list
slow = head
fast = head
# Find the middle of the linked list using the slow and fast pointers
while fast and fast.next:
# move slow one step forward
slow = slow.next
# move fast two steps forward
fast = fast.next.next
# Reverse the second half of the linked list starting from the middle node
revert_data = reverse_linked_list(slow)
# Compare the first half of the linked list with the reversed second half of the linked list
check = compare_two_halves(head, revert_data)
# Re-reverse the second half of the linked list to restore the original linked list
reverse_linked_list(revert_data)
# Return True if the linked list is a palindrome, else False
if check:
return True
return False
def compare_two_halves(first_half, second_half):
# Compare the corresponding nodes of the first and second halves of the linked list
while first_half and second_half:
if first_half.val != second_half.val:
return False
else:
first_half = first_half.next
second_half = second_half.next
return True
Maximum Twin Sum of a Linked List
Problem Statement
Find the maximum twin sum in a linked list with even number of nodes.
Concept Definition
- Twin Nodes: Paired nodes from opposite ends
- Twin Sum: Sum of values of twin nodes
- Goal: Determine maximum twin sum
Solution
The main idea behind finding the maximum twin sum in a linked list is to reverse the second half of the list and sum the corresponding values from both halves. The algorithm first locates the middle node using fast and slow pointers to achieve this. Then, it reverses the second half of the linked list, starting from the middle node. After that, it calculates the twin sums by adding the values of the nodes from the start of the list and the reversed second half while keeping track of the maximum sum found so far. Finally, it returns the maximum sum encountered during the traversal.
def twin_sum(head):
# Initialize fast and slow pointers at the head of the linked list
slow, fast = head, head
# Find the middle node of the linked list using fast and slow pointers
while fast and fast.next:
# Move the slow pointer one step forward
slow = slow.next
# Move the fast pointer two steps forward
fast = fast.next.next
# Set curr at the middle node (slow) to reverse the second half of the linked list
curr, prev = slow, None
# Iterate through the list until curr reaches NULL
while curr:
# Save curr.next for later use
temp = curr.next
curr.next = prev
prev = curr
curr = temp
# Initialize max_sum with 0 to keep track of the maximum twin sum found so far
max_sum = 0
# Set curr at the head of the linked list
curr = head
# Iterate through the list until prev reaches NULL
while prev:
# Update max_sum if the current twin sum is greater than max_sum
max_sum = max(max_sum, curr.val + prev.val)
# Move both prev and curr pointers forward
prev = prev.next
curr = curr.next
# Return max_sum as the maximum twin sum of the given linked list
return max_sum
