# Fast & Slow pointers introduction

The Fast & Slow pointer approach, also known as the Hare & Tortoise algorithm, is a pointer algorithm that uses two pointers which move through the array (or sequence/LinkedList) at different speeds. This approach is quite useful when dealing with cyclic LinkedLists or arrays.

By moving at different speeds (say, in a cyclic LinkedList), the algorithm proves that the two pointers are bound to meet. The fast pointer should catch the slow pointer once both the pointers are in a cyclic loop.

One of the famous problems solved using this technique was Finding a cycle in a LinkedList.

## Simple problems

Given the head of a Singly LinkedList, write a function to determine if the LinkedList has a cycle in it or not.

Imagine two racers running on a circular racing track. If one racer is faster than the other, the faster racer is bound to catch up and cross the slower racer from behind. We can use this fact to devise an algorithm to determine if a LinkedList has a cycle in it or not.

Imagine we have a slow and a fast pointer to traverse the LinkedList. In each iteration, the slow pointer moves one step and the fast pointer moves two steps. This gives us two conclusions:

1. If the LinkedList doesn’t have a cycle in it, the fast pointer will reach the end of the LinkedList before the slow pointer to reveal that there is no cycle in the LinkedList.
2. The slow pointer will never be able to catch up to the fast pointer if there is no cycle in the LinkedList.

If the LinkedList has a cycle, the fast pointer enters the cycle first, followed by the slow pointer. After this, both pointers will keep moving in the cycle infinitely. If at any stage both of these pointers meet, we can conclude that the LinkedList has a cycle in it.

why will they meet?

https://youtu.be/gBTe7lFR3vc?t=446

"""

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer.
Internally, pos is used to denote the index of the node that tail's next pointer is connected to.
Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.

https://www.notion.so/paulonteri/Hare-Tortoise-Algorithm-1020d217ffb54e47b7aea3c175d75618#0f0930e961414b1e90871b4efbe3d1b6
"""

class ListNode:
def __init__(self, x):
self.val = x
self.next = None

class Solution:
return False

# move to initial positions
if fast is None:
return False
fast = fast.next

while fast != None:
if fast == slow:
return True

slow = slow.next
fast = fast.next
if fast:
fast = fast.next

return False


Given the head of a LinkedList with a cycle, find the length of the cycle.

"""
Once the fast and slow pointers meet,
we can save the slow pointer and iterate the whole cycle with another pointer
until we see the slow pointer again to find the length of the cycle.
"""

class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next

while fast is not None and fast.next is not None:
fast = fast.next.next
slow = slow.next
if slow == fast:  # found the cycle
return calculate_cycle_length(slow)

return 0

def calculate_cycle_length(slow):
current = slow
cycle_length = 0
while True:
current = current.next
cycle_length += 1
if current == slow:
break
return cycle_length


## Problem

Given the head of a Singly LinkedList that contains a cycle, write a function to find the starting node of the cycle.

## Solution

If we know the length of the LinkedList cycle, we can find the start of the cycle through the following steps:

1. Take two pointers. Let’s call them pointer1 and pointer2.
2. Initialize both pointers to point to the start of the LinkedList.
3. We can find the length of the LinkedList cycle using the approach discussed in Length of LinkedList Cycle. Let’s assume that the length of the cycle is ‘K’ nodes.
4. Move pointer2 ahead by ‘K’ nodes.
5. Now, keep incrementing pointer1 and pointer2 until they both meet.
6. Imagine the cycle as a circular track: As pointer2 is ‘K’ nodes ahead of pointer1, which means, pointer2 must have completed one loop in the cycle when both pointers meet. Their meeting point will be the start of the cycle.
• if pointer2 is ‘K’ nodes ahead of pointer1, it means that when pointer1 will be at the start of the cycle, pointer2 two will be at the end - they are the same node

## Code

"""
Find start of linked list cycle:

Given the head of a Singly LinkedList that contains a cycle, write a function to find the starting node of the cycle.
https://www.educative.io/courses/grokking-the-coding-interview/N7pvEn86YrN
https://www.notion.so/paulonteri/Hare-Tortoise-Algorithm-1020d217ffb54e47b7aea3c175d75618#0f0930e961414b1e90871b4efbe3d1b6
"""

"""

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer.
Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Notice that you should not modify the linked list
https://www.algoexpert.io/questions/Find%20Loop
https://www.notion.so/paulonteri/Hare-Tortoise-Algorithm-1020d217ffb54e47b7aea3c175d75618#0f0930e961414b1e90871b4efbe3d1b6
"""

class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next

cycle_length = 0
while (fast is not None and fast.next is not None):
fast = fast.next.next
slow = slow.next
if slow == fast:  # found the cycle
cycle_length = calculate_cycle_length(slow)
break

def calculate_cycle_length(slow):
current = slow
cycle_length = 0
while True:
current = current.next
cycle_length += 1
if current == slow:
break
return cycle_length

# move pointer2 ahead 'cycle_length' nodes
while cycle_length > 0:
pointer2 = pointer2.next
cycle_length -= 1

# increment both pointers until they meet at the start of the cycle
while pointer1 != pointer2:
pointer1 = pointer1.next
pointer2 = pointer2.next

return pointer1

class Solution:
return None

# # find cycle
while True:
if fast is None or fast.next is None:  # find invalid
return None

slow = slow.next
fast = fast.next.next
if slow == fast:
break

# # find start of cycle
# the (dist) head to the start of the cycle ==
#   the (dist) meeting point to the start of the cycle
two = fast
while one != two:
one = one.next
two = two.next
return one

"""
Find Loop:
Write a function that takes in the head of a Singly Linked List that contains a loop
(in other words, the list's tail node points to some node in the list instead of None / null).
The function should return the node (the actual node--not just its value) from which the loop originates in constant space.
Each LinkedList node has an integer value as well as a next node pointing to the next node in the list.

Sample Input
head = 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 // the head node with value 0
^         v
9 <- 8 <- 7
Sample Output
4 -> 5 -> 6 // the node with value 4
^         v
9 <- 8 <- 7
https://www.algoexpert.io/questions/Find%20Loop
"""

# This is an input class. Do not edit.
def __init__(self, value):
self.value = value
self.next = None

# .next to allow the first loop to work

# find meeting point
while p_two != p_one:
p_one = p_one.next
p_two = p_two.next.next

# # find start of cycle
# the (dist) head to the start of the cycle ==
#   the (dist) meeting point to the start of the cycle
while p_two != p_one:
p_one = p_one.next
p_two = p_two.next

return p_one


## Time & Space complexity

As we know, finding the cycle in a LinkedList with ‘N’ nodes and also finding the length of the cycle requires O(N). Also, as we saw in the above algorithm, we will need O(N) to find the start of the cycle. Therefore, the overall time complexity of our algorithm will be O(N).

# Happy Number

## Problem

Try doing it in constant space

"""
Happy Number:

Any number will be called a happy number if,
after repeatedly replacing it with a number equal to the sum of the square of all of its digits, leads us to number ‘1’.
All other (not-happy) numbers will never reach ‘1’. Instead, they will be stuck in a cycle of numbers which does not include ‘1’.

Example 1:
Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
Example 2:
Input: n = 2
Output: false
Example 3:
Input: 23
Output: true (23 is a happy number)
Explanations: Here are the steps to find out that 23 is a happy number:
Example 4:
Input: 12
Output: false (12 is not a happy number)
Explanations: Here are the steps to find out that 12 is not a happy number:

"""


## Solution

The process, defined above, to find out if a number is a happy number or not, always ends in a cycle. If the number is a happy number, the process will be stuck in a cycle on number ‘1,’ and if the number is not a happy number then the process will be stuck in a cycle with a set of numbers.

We saw in the LinkedList Cycle problem that we can use the Fast & Slow pointers method to find a cycle among a set of elements. As we have described above, each number will definitely have a cycle. Therefore, we will use the same fast & slow pointer strategy to find the cycle and once the cycle is found, we will see if the cycle is stuck on number ‘1’ to find out if the number is happy or not.

### Brute force

def square_of_digits(num):
res = 0
while num > 0:
res += (num % 10) * (num % 10)
num = num // 10
return res

# using memory
def find_happy_number_01(num):
store = set()
while num != 1:
num = square_of_digits(num)
if num in store:
return False

return True


### Optimal

def square_of_digits(num):
res = 0
while num > 0:
res += (num % 10) * (num % 10)
num = num // 10
return res

def find_happy_number(num):
fast = num
slow = num
loop_started = False
while slow != fast or not loop_started:
loop_started = True
fast = square_of_digits(square_of_digits(fast))
slow = square_of_digits(slow)
if slow == 1 or fast == 1:
return True

return False