🚀 Day 2: Cracking the Two Pointers Pattern (Amazon Interview Series)

The Two Pointers Pattern is a favorite at Amazon because it turns O(n²) problems into O(n) by smartly moving two indices instead of brute-forcing all pairs.

---

🔑 What is the Two Pointers Pattern?

• Place one pointer at the start and another at the end (or both at the start but moving differently).
• Move pointers based on conditions (sum too big, character mismatch, zero encountered, etc).
• Works beautifully on sorted arrays, linked lists, and strings.

When Amazon uses this:

• Pair problems (sum, difference, product)
• Removing duplicates efficiently
• Sorting and merging scenarios
• String palindrome checks

---

📝 Problem 1: Two Sum II (Input Sorted)

👉 Amazon-style phrasing:
Given a sorted array of integers and a target value, return the indices (1-based) of the two numbers that add up to the target.

Java Solution

public class TwoSumSorted {
    public static 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};
            else if (sum < target) left++;
            else right--;
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;
        int[] result = twoSum(nums, target);
        System.out.println(result[0] + ", " + result[1]); // Output: 1, 2
    }
}

✅ Time Complexity: O(n)

---

📝 Problem 2: Container With Most Water

👉 Amazon-style phrasing:
Given n vertical lines, find two lines that together hold the maximum amount of water.

Java Solution

public class MaxWaterContainer {
    public static int maxArea(int[] height) {
        int left = 0, right = height.length - 1, maxArea = 0;

        while (left < right) {
            int h = Math.min(height[left], height[right]);
            int area = h * (right - left);
            maxArea = Math.max(maxArea, area);

            // Move the pointer at smaller height
            if (height[left] < height[right]) left++;
            else right--;
        }
        return maxArea;
    }

    public static void main(String[] args) {
        int[] height = {1,8,6,2,5,4,8,3,7};
        System.out.println(maxArea(height)); // Output: 49
    }
}

✅ Time Complexity: O(n)
✅ Why Amazon asks: Efficiency in maximizing constraints while minimizing loops.

---

📝 Problem 3: 3Sum

👉 Amazon-style phrasing:
Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c = 0.

Java Solution

import java.util.*;

public class ThreeSum {
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < nums.length - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicates
            int left = i + 1, right = nums.length - 1;

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == 0) {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (sum < 0) left++;
                else right--;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        System.out.println(threeSum(nums)); // Output: [[-1, -1, 2], [-1, 0, 1]]
    }
}

✅ Time Complexity: O(n²)
✅ Why Amazon asks: Combination of sorting + two pointers — efficiency and correctness.

---

📝 Problem 4: Move Zeroes

👉 Amazon-style phrasing:
Move all 0s to the end of the array while keeping the relative order of non-zero elements.

Java Solution

public class MoveZeroes {
    public static void moveZeroes(int[] nums) {
        int insertPos = 0;
        for (int num : nums) {
            if (num != 0) nums[insertPos++] = num;
        }
        while (insertPos < nums.length) {
            nums[insertPos++] = 0;
        }
    }

    public static void main(String[] args) {
        int[] nums = {0,1,0,3,12};
        moveZeroes(nums);
        System.out.println(Arrays.toString(nums)); // Output: [1, 3, 12, 0, 0]
    }
}

✅ Time Complexity: O(n)
✅ Why Amazon asks: Tests array manipulation skill with minimal space.

---

📝 Problem 5: Valid Palindrome (Ignoring Non-Alphanumeric)

👉 Amazon-style phrasing:
Check if a given string is a valid palindrome, ignoring non-alphanumeric characters and case.

Java Solution

public class ValidPalindrome {
    public static boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) left++;
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) right--;

            if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

    public static void main(String[] args) {
        String s = "A man, a plan, a canal: Panama";
        System.out.println(isPalindrome(s)); // Output: true
    }
}

✅ Time Complexity: O(n)
✅ Why Amazon asks: Classic string + two pointers check, tests handling of edge cases.

---

📚 Extended Problem List (Practice for Readers)

1. Remove Duplicates from Sorted Array – In-place removal using two pointers.
2. Dutch National Flag Problem – Sort colors (0,1,2) in-place.
3. 4Sum Problem – Extension of 3Sum with two pointers inside loops.
4. Minimum Difference Pair – Find closest pair between two sorted arrays.
5. Backspace String Compare – Simulate string typing with # as backspace.

---

🎯 Key Takeaways

• Two pointers = pair optimization.
• Most efficient on sorted arrays or when order is controlled.
• Amazon asks these to test: thinking in terms of movement, not brute force enumeration.

---

📅 Next in the series (Day 3):
👉 Fast & Slow Pointers Pattern – used in cycle detection, linked list tricks, and number puzzles.