Two Pointer Pattern: Solve Interview Problems Faster With Less Code

public class TwoSumSorted {

    /**
     * Given a SORTED array of integers and a target sum,
     * return the 1-based indices of the two numbers that add up to the target.
     * Assumes exactly one solution exists.
     *
     * Time:  O(n)  — single pass with two pointers
     * Space: O(1)  — no extra data structures
     */
    public static int[] findPairWithTargetSum(int[] sortedNumbers, int targetSum) {
        int leftIndex = 0;                          // Start at the smallest element
        int rightIndex = sortedNumbers.length - 1;  // Start at the largest element

        while (leftIndex < rightIndex) {
            int currentSum = sortedNumbers[leftIndex] + sortedNumbers[rightIndex];

            if (currentSum == targetSum) {
                // Found it — return 1-based indices as the problem specifies
                return new int[]{leftIndex + 1, rightIndex + 1};
            }

            if (currentSum < targetSum) {
                // Sum is too small — we need a bigger left value, so move left pointer right
                leftIndex++;
            } else {
                // Sum is too large — we need a smaller right value, so move right pointer left
                rightIndex--;
            }
        }

        // Problem guarantees a solution exists, but good practice to handle this
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[] prices = {2, 7, 11, 15};
        int budget = 9;

        int[] result = findPairWithTargetSum(prices, budget);
        System.out.println("Indices (1-based): [" + result[0] + ", " + result[1] + "]");
        System.out.println("Values: " + prices[result[0]-1] + " + " + prices[result[1]-1] + " = " + budget);

        // Second test case
        int[] scores = {1, 3, 4, 5, 7, 10, 11};
        int targetScore = 9;
        int[] scoreResult = findPairWithTargetSum(scores, targetScore);
        System.out.println("\nIndices (1-based): [" + scoreResult[0] + ", " + scoreResult[1] + "]");
        System.out.println("Values: " + scores[scoreResult[0]-1] + " + " + scores[scoreResult[1]-1] + " = " + targetScore);
    }
}

public class RemoveDuplicatesInPlace {

    /**
     * Remove duplicates from a sorted array IN-PLACE.
     * Returns the count of unique elements.
     * Elements beyond the returned count don't matter.
     *
     * Time:  O(n)  — single pass
     * Space: O(1)  — no extra arrays or sets
     *
     * Key constraint: the array is SORTED, so duplicates are always adjacent.
     * That's what makes the two-pointer approach valid here.
     */
    public static int removeDuplicates(int[] sortedArray) {
        if (sortedArray.length == 0) return 0;

        // slowWriter points to where the next unique element should be written
        int slowWriter = 0;

        // fastReader scouts ahead to find the next unique element
        for (int fastReader = 1; fastReader < sortedArray.length; fastReader++) {

            // If fastReader found a new unique value (different from what slowWriter last wrote)...
            if (sortedArray[fastReader] != sortedArray[slowWriter]) {
                slowWriter++;  // Advance slowWriter to the next available slot
                sortedArray[slowWriter] = sortedArray[fastReader];  // Write the unique value there
            }
            // If they're equal, fastReader keeps moving — we skip the duplicate
        }

        return slowWriter + 1;  // +1 because slowWriter is an index, not a count
    }

    public static void main(String[] args) {
        int[] temperatures = {1, 1, 2, 3, 3, 3, 4, 5, 5};

        System.out.println("Before: " + java.util.Arrays.toString(temperatures));

        int uniqueCount = removeDuplicates(temperatures);

        System.out.println("Unique count: " + uniqueCount);
        System.out.print("Unique elements: ");
        for (int i = 0; i < uniqueCount; i++) {
            System.out.print(temperatures[i] + " ");
        }
        System.out.println();

        // Edge case: all elements are the same
        int[] allSame = {7, 7, 7, 7};
        int allSameCount = removeDuplicates(allSame);
        System.out.println("\nAll-same array unique count: " + allSameCount);
        System.out.println("First unique element: " + allSame[0]);

        // Edge case: no duplicates at all
        int[] noDupes = {1, 2, 3, 4};
        int noDupesCount = removeDuplicates(noDupes);
        System.out.println("\nNo-duplicate array unique count: " + noDupesCount);
    }
}

public class LinkedListCycleDetector {

    // Standard linked list node
    static class ListNode {
        int value;
        ListNode next;

        ListNode(int value) {
            this.value = value;
            this.next = null;
        }
    }

    /**
     * Detect whether a linked list contains a cycle.
     * Uses Floyd's fast-slow pointer algorithm.
     *
     * Time:  O(n) — in the worst case we traverse the list once
     * Space: O(1) — only two pointer variables, no extra storage
     */
    public static boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;  // A list with 0 or 1 nodes can't have a cycle
        }

        ListNode slowRunner = head;       // Moves 1 step at a time
        ListNode fastRunner = head;       // Moves 2 steps at a time

        while (fastRunner != null && fastRunner.next != null) {
            slowRunner = slowRunner.next;        // 1 step
            fastRunner = fastRunner.next.next;   // 2 steps

            // If they ever point to the same node, a cycle exists
            if (slowRunner == fastRunner) {
                return true;  // They've met inside the cycle
            }
        }

        // fastRunner reached the end — no cycle
        return false;
    }

    /**
     * Bonus: find WHERE the cycle starts (common interview follow-up).
     * After detection, reset slow to head and move both one step at a time.
     * They meet at the cycle entry point.
     */
    public static ListNode findCycleStart(ListNode head) {
        ListNode slowRunner = head;
        ListNode fastRunner = head;

        // Phase 1: detect the cycle
        while (fastRunner != null && fastRunner.next != null) {
            slowRunner = slowRunner.next;
            fastRunner = fastRunner.next.next;
            if (slowRunner == fastRunner) {
                // Phase 2: find the entry point
                // Reset slow to head; fast stays at meeting point
                ListNode entryFinder = head;
                while (entryFinder != slowRunner) {
                    entryFinder = entryFinder.next;
                    slowRunner = slowRunner.next;
                }
                return entryFinder;  // This is the start of the cycle
            }
        }
        return null;  // No cycle
    }

    public static void main(String[] args) {
        // Build: 3 -> 2 -> 0 -> -4
        //                ^         |
        //                |_________| (cycle back to node with value 2)
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(0);
        ListNode node4 = new ListNode(-4);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node2;  // Creates the cycle — tail points back to node2

        System.out.println("Has cycle: " + hasCycle(node1));  // true

        ListNode cycleStart = findCycleStart(node1);
        System.out.println("Cycle starts at node with value: " + cycleStart.value);  // 2

        // Now test a list with no cycle
        ListNode linearHead = new ListNode(1);
        linearHead.next = new ListNode(2);
        linearHead.next.next = new ListNode(3);

        System.out.println("\nLinear list has cycle: " + hasCycle(linearHead));  // false
        System.out.println("Cycle start (should be null): " + findCycleStart(linearHead));  // null
    }
}