Two Pointer Bug: Unsorted Data Skips Valid Pairs

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
    }
}

public class ContainerWithMostWater {

    /**
     * Find the maximum area of water a container can hold.
     * Given an array of heights, find two lines that form the maximum area.
     *
     * Time:  O(n) — single pass
     * Space: O(1)
     */
    public static int maxArea(int[] height) {
        int left = 0;
        int right = height.length - 1;
        int maxArea = 0;

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

            // Move the pointer with the shorter line inward
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }

        return maxArea;
    }

    public static void main(String[] args) {
        int[] heights = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        int result = maxArea(heights);
        System.out.println("Max area: " + result);  // Expected 49 (between 8 and 7 at indices 1 and 8)

        // Edge case: two lines
        int[] twoLines = {1, 2};
        System.out.println("Two lines max area: " + maxArea(twoLines));  // 1

        // Edge case: all same height
        int[] sameHeight = {5, 5, 5, 5};
        System.out.println("Same height max area: " + maxArea(sameHeight));  // 15 (between first and last)
    }
}

import java.util.*;

public class ThreeSum {

    /**
     * Find all unique triplets that sum to zero.
     * Uses sorting + two-pointer for the inner pair.
     *
     * Time:  O(n²)
     * Space: O(1) extra (excluding output)
     */
    public static List<List<Integer>> findTriplets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length - 2; i++) {
            // Skip duplicate values for the fixed element
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1;
            int right = nums.length - 1;
            int target = -nums[i];

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

    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> triplets = findTriplets(nums);
        System.out.println("Unique triplets: " + triplets);
        // Expected: [[-1, -1, 2], [-1, 0, 1]]

        // Edge case: all zeros
        int[] zeros = {0, 0, 0, 0};
        System.out.println("All zeros triplets: " + findTriplets(zeros));
        // Expected: [[0, 0, 0]]
    }
}

public class PalindromeChecker {

    /**
     * Check if a string is a palindrome (alphanumeric only, case-insensitive).
     * Uses opposite-ends two pointers.
     *
     * Time:  O(n)
     * Space: O(1)
     */
    public static boolean isPalindrome(String s) {
        if (s == null) return false;
        int left = 0;
        int right = s.length() - 1;

        while (left < right) {
            // Skip non-alphanumeric characters from left
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            // Skip non-alphanumeric characters from right
            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) {
        System.out.println(isPalindrome("A man, a plan, a canal: Panama"));  // true
        System.out.println(isPalindrome("race a car"));  // false
        System.out.println(isPalindrome(" "));  // true
        System.out.println(isPalindrome("ab_a"));  // true
    }
}