🚀 Day 3: Cracking the Fast & Slow Pointers Pattern (Amazon Interview Series)

The Fast & Slow Pointers Pattern (also called Floyd’s Cycle Detection) uses two pointers moving at different speeds — usually one moves 1 step at a time (slow) and the other moves 2 steps at a time (fast).

If they ever meet, a cycle exists.
If the fast pointer reaches the end, there’s no cycle.

---

🔑 When to Use Fast & Slow Pointers?

• Detect cycles in linked lists
• Find starting point of a cycle
• Find middle element of a linked list
• Solve number problems that repeat (e.g., Happy Number)

Amazon tests this because it’s space-efficient (O(1) space) and avoids hashing.

---

📝 Problem 1: Detect Cycle in Linked List

👉 Amazon-style phrasing:
Given the head of a linked list, determine if the list has a cycle.

Java Solution

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class LinkedListCycle {
    public static boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) return true; // cycle detected
        }
        return false;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(3);
        head.next = new ListNode(2);
        head.next.next = new ListNode(0);
        head.next.next.next = new ListNode(-4);
        head.next.next.next.next = head.next; // cycle

        System.out.println(hasCycle(head)); // Output: true
    }
}

✅ Time Complexity: O(n)
✅ Space Complexity: O(1)

---

📝 Problem 2: Find Start of Cycle

👉 Amazon-style phrasing:
Modify the previous problem — if a cycle exists, return the node where the cycle begins.

Java Solution

public class LinkedListCycleStart {
    public static ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;

        // Step 1: Detect cycle
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) break;
        }

        // No cycle
        if (fast == null || fast.next == null) return null;

        // Step 2: Move one pointer to head
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow; // start of cycle
    }
}

✅ Key Amazon insight: This tests if you know the math behind Floyd’s algorithm — when slow and fast meet, moving one to head and advancing both by one step will give the cycle start.

---

📝 Problem 3: Find Middle of Linked List

👉 Amazon-style phrasing:
Given a linked list, return the middle node. If there are two middle nodes, return the second one.

Java Solution

public class MiddleOfLinkedList {
    public static ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

✅ Why Amazon likes this:
Shows if you can use pointer speed differences beyond just cycle detection.

---

📝 Problem 4: Happy Number

👉 Amazon-style phrasing:
Write an algorithm to determine if a number is a happy number. A happy number is a number that eventually reaches 1 after repeatedly replacing it with the sum of the squares of its digits. If it loops forever, it’s not happy.

Java Solution

public class HappyNumber {
    private static int nextNumber(int n) {
        int sum = 0;
        while (n > 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }

    public static boolean isHappy(int n) {
        int slow = n, fast = n;
        do {
            slow = nextNumber(slow);
            fast = nextNumber(nextNumber(fast));
        } while (slow != fast);

        return slow == 1;
    }

    public static void main(String[] args) {
        System.out.println(isHappy(19)); // Output: true
        System.out.println(isHappy(2));  // Output: false
    }
}

✅ Time Complexity: O(log n) per step
✅ Why Amazon asks: This disguises cycle detection in a mathy problem.

---

📚 Extended Problem List (Practice)

1. Linked List Cycle II (LeetCode 142) – Find start of cycle (covered above).
2. Reorder List – Find middle + reverse second half + merge.
3. Palindrome Linked List – Find middle + reverse + compare halves.
4. Detect Circular Array Loop – Variation of cycle detection in arrays.
5. Tortoise & Hare on Graphs – Extension to detect loops in graph traversal.

---

🎯 Key Takeaways

• Fast & Slow pointers = detect patterns by speed difference.
• Always O(1) space — Amazon loves memory-efficient solutions.
• Works in linked lists, arrays, and math problems.

---

📅 Next in the series (Day 4):
👉 Merge Intervals Pattern – Amazon’s favorite for scheduling, calendar, and meeting room problems.