📌 FAANG Coding Patterns Series – Day 2

Pattern: Two Pointers & Fast-Slow Pointers

---

🔹 Why This Pattern?

Two Pointers (and its fast-slow variant) is one of the most frequently tested patterns across FAANG interviews. It appears in:

• Arrays → sorted arrays, pair-sums, container problems.
• Strings → palindrome checks, valid substring problems.
• Linked Lists → cycle detection, middle node, removing N-th node.
• Intervals → merging, intersecting timelines.

It is optimal in problems where brute force = O(n²), but two pointers optimize to O(n).

---

🔥 Sub-Patterns

---

1️⃣ Opposite-End Pointers (Left-Right Shrink)

Best for sorted arrays and string palindrome checks.

Example: Two Sum II – Input Sorted Array (Amazon/Apple)

Find two numbers in a sorted array that sum up to target.

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1}; // 1-indexed
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return new int[]{-1, -1};
    }
}

Complexity: O(n) time, O(1) space.

---

2️⃣ Fast & Slow Pointers (Linked List Magic)

Used for cycle detection, finding middle, or removing nth node.

Example: Detect Cycle in Linked List (Google/Amazon)

Classic Floyd’s Cycle Detection (Tortoise and Hare).

class Solution {
    public 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;
        }
        return false;
    }
}

---

3️⃣ Sliding Two Pointers (Shrink/Grow Window)

Used in strings/arrays where we shrink/grow a window.

Example: Container With Most Water (Meta/Apple)

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int max = 0;
        while (left < right) {
            int area = (right - left) * Math.min(height[left], height[right]);
            max = Math.max(max, area);
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return max;
    }
}

---

📌 Flagship Problems by Company

Problem	Company	Pattern	Difficulty
Linked List Cycle	Google, Amazon	Fast-Slow	Easy
Middle of Linked List	Google	Fast-Slow	Easy
Remove N-th Node from End	Amazon, Meta	Fast-Slow	Medium
Two Sum II (Sorted)	Amazon, Apple	Opposite-End	Easy
Valid Palindrome II	Google	Opposite-End	Easy/Medium
3Sum	Meta, Amazon	Opposite-End + Sorting	Medium
Container With Most Water	Meta, Apple	Opposite-End	Medium
Trapping Rain Water (2-pointer version)	Apple, Meta	Opposite-End	Hard
Interval Intersection	Netflix	Two Pointers	Medium

---

🧠 Quick “Pattern Recognition” Checklist

• Array sorted? → Think two pointers from both ends.
• Linked list cycle/middle/removal? → Fast/Slow pointers.
• Palindrome/string check? → Left/right pointer shrink.
• Interval problems? → Two pointers across both lists.

---

🎯 Practice Set (Homework with Hints)

1. Linked List Cycle II (Google/Amazon) – Return cycle start node.
   Hint: After meeting point, reset one pointer to head.

2. Remove Nth Node from End of List (Amazon/Meta) – Use fast pointer n ahead.

3. Valid Palindrome II (Google) – Allow one mismatch and retry by skipping either side.

4. 3Sum Closest (Meta) – Sort array, fix one, use two pointers inside.

5. Trapping Rain Water (Two Pointers) (Apple/Meta) – Maintain leftMax, rightMax.

---

🔑 Key Takeaway

Two pointers are like a Swiss Army Knife for FAANG interviews.
If you see sorted arrays, linked lists, palindromes, or intervals, 90% chance the solution involves this pattern.

---

📅 Coming Up – Day 3:
👉 Prefix Sum + Difference Arrays + Hybrid Patterns (very Google/Amazon heavy).

---