Two Pointer Technique — O(n²) Timeout on 120K Transactions

package io.thecodeforge.algo;

/**
 * Summary of the three core two-pointer patterns.
 * Each pattern reduces O(n²) nested loops to O(n) single-pass logic.
 */
public class TwoPointerPatternSummary {

    /*
     * PATTERN 1: Opposite Ends
     * ─────────────────────: left=0, right=n-1
     * Movement: move left right or right left based on comparison
     * Requirement: sorted array (for numeric problems)
     * Time: O(n), Space: O(1)
     * Examples: Two Sum II, Container With Most Water, Valid Palindrome
     */

    /*
     * PATTERN 2: Slow-Fast (Read-Write)
     * ──────────────────────────────────
     * Setup: slow=0 (write position), fast=0 (scanner)
     * Movement: fast always advances. slow advances only when a valid element is found.
     * Requirement: none (works on unsorted input)
     * Time: O(n), Space: O(1)
     * Examples: Remove Duplicates, Remove Element, Move Zeroes
     */

    /*
     * P───
     * SetupATTERN 3: Sliding Window
     * ─────────────────────────
     * Setup: left=0, right=0
     * Movement: right always advances. left advances when constraint is violated.
     * Requirement: constraint must be incrementally maintainable (HashSet, counter, sum)
     * Time: O(n), Space: O(k) where k is alphabet or constraint size
     * Examples: Longest Substring Without Repeating, Minimum Window Substring
     */

    public static void main(String[] args) {
        System.out.println("Two Pointer Patterns:");
        System.out.println("1. Opposite Ends  — sorted arrays, pair/triplet finding");
        System.out.println("2. Slow-Fast      — in-place filtering, cycle detection");
        System.out.println("3. Sliding Window — substring/subarray optimization");
        System.out.println("\nAll three reduce O(n²) to O(n) by eliminating redundant comparisons.");
    }
}

package io.thecodeforge.algo;

public class TwoSumSortedArray {

    /**
     * Finds indices of two numbers in a sorted array that add up to the target.
     * Uses opposite-end two pointers — O(n) time, O(1) space.
     */
    public static int[] findPairWithTargetSum(int[] sortedNumbers, int target) {
        int leftIndex = 0;
        int rightIndex = sortedNumbers.length - 1;

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

            if (currentSum == target) {
                return new int[]{leftIndex + 1, rightIndex + 1};
            } else if (currentSum < target) {
                leftIndex++;
            } else {
                rightIndex--;
            }
        }

        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[] bookPageCounts = {120, 230, 280, 370, 450, 500, 620};
        int targetPages = 750;

        int[] result = findPairWithTargetSum(bookPageCounts, targetPages);

        if (result[0] != -1) {
            System.out.println("Pair found at positions " + result[0] + " and " + result[1]);
            System.out.println("Values: " + bookPageCounts[result[0] - 1]
                               + " + " + bookPageCounts[result[1] - 1]
                               + " = " + targetPages);
        } else {
            System.out.println("No pair adds up to " + targetPages);
        }

        int[] noResult = findPairWithTargetSum(bookPageCounts, 9999);
        System.out.println("\nImpossible target result: ["
                           + noResult[0] + ", " + noResult[1] + "]");
    }
}

package io.thecodeforge.algo;

public class PalindromeAndInPlaceRemoval {

    // ── Part 1: Valid Palindrome (ignoring non-alphanumeric chars) ─────────────

    public static boolean isValidPalindrome(String sentence) {
        int leftIndex = 0;
        int rightIndex = sentence.length() - 1;

        while (leftIndex < rightIndex) {
            while (leftIndex < rightIndex
                    && !Character.isLetterOrDigit(sentence.charAt(leftIndex))) {
                leftIndex++;
            }
            while (leftIndex < rightIndex
                    && !Character.isLetterOrDigit(sentence.charAt(rightIndex))) {
                rightIndex--;
            }

            if (Character.toLowerCase(sentence.charAt(leftIndex))
                    != Character.toLowerCase(sentence.charAt(rightIndex))) {
                return false;
            }

            leftIndex++;
            rightIndex--;
        }
        return true;
    }

    // ── Part 2: Remove all instances of a value in-place ──────────────────────

    public static int removeValueInPlace(int[] numbers, int valueToRemove) {
        int writePosition = 0;

        for (int readPosition = 0; readPosition < numbers.length; readPosition++) {
            if (numbers[readPosition] != valueToRemove) {
                numbers[writePosition] = numbers[readPosition];
                writePosition++;
            }
        }

        return writePosition;
    }

    public static void main(String[] args) {
        String phrase1 = "A man, a plan, a canal: Panama";
        String phrase2 = "race a car";

        System.out.println("'" + phrase1 + "' is palindrome: " + isValidPalindrome(phrase1));
        System.out.println("'" + phrase2 + "' is palindrome: " + isValidPalindrome(phrase2));

        int[] scores = {3, 2, 2, 3, 4, 3, 5};
        int removeTarget = 3;

        System.out.println("\nOriginal scores array length: " + scores.length);
        int newLength = removeValueInPlace(scores, removeTarget);

        System.out.print("After removing all " + removeTarget + "s — ");
        System.out.print("new length: " + newLength + ", elements: ");
        for (int i = 0; i < newLength; i++) {
            System.out.print(scores[i] + (i < newLength - 1 ? ", " : "\n"));
        }
    }
}

package io.thecodeforge.algo;

import java.util.HashMap;
import java.util.Map;

public class LongestUniqueSubstring {

    public static int longestNonRepeatingLength(String text) {
        Map<Character, Integer> lastSeenAtIndex = new HashMap<>();

        int maxLength = 0;
        int windowStart = 0;

        for (int windowEnd = 0; windowEnd < text.length(); windowEnd++) {
            char currentChar = text.charAt(windowEnd);

            if (lastSeenAtIndex.containsKey(currentChar)
                    && lastSeenAtIndex.get(currentChar) >= windowStart) {
                windowStart = lastSeenAtIndex.get(currentChar) + 1;
            }

            lastSeenAtIndex.put(currentChar, windowEnd);

            int currentWindowLength = windowEnd - windowStart + 1;
            maxLength = Math.max(maxLength, currentWindowLength);
        }

        return maxLength;
    }

    public static String longestNonRepeatingSubstring(String text) {
        Map<Character, Integer> lastSeenAtIndex = new HashMap<>();
        int maxLength = 0;
        int windowStart = 0;
        int bestWindowStart = 0;

        for (int windowEnd = 0; windowEnd < text.length(); windowEnd++) {
            char currentChar = text.charAt(windowEnd);

            if (lastSeenAtIndex.containsKey(currentChar)
                    && lastSeenAtIndex.get(currentChar) >= windowStart) {
                windowStart = lastSeenAtIndex.get(currentChar) + 1;
            }

            lastSeenAtIndex.put(currentChar, windowEnd);

            int currentWindowLength = windowEnd - windowStart + 1;
            if (currentWindowLength > maxLength) {
                maxLength = currentWindowLength;
                bestWindowStart = windowStart;
            }
        }

        return text.substring(bestWindowStart, bestWindowStart + maxLength);
    }

    public static void main(String[] args) {
        String[] testInputs = {
            "abcabcbb",
            "bbbbb",
            "pwwkew",
            "theCodeForge"
        };

        for (String input : testInputs) {
            int length = longestNonRepeatingLength(input);
            String substring = longestNonRepeatingSubstring(input);
            System.out.printf("Input: %-15s → Length: %d, Substring: \"%s\"%n",
                              "\"" + input + "\"", length, substring);
        }
    }
}

package io.thecodeforge.algo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSumSolver {

    /**
     * Finds all unique triplets in the array that sum to zero.
     * Sort + fix one element + two pointers on remainder.
     * O(n²) time, O(1) space excluding output.
     */
    public static List<int[]> findAllTripletsSummingToZero(int[] nums) {
        List<int[]> triplets = new ArrayList<>();
        Arrays.sort(nums); // Sort first — enables two-pointer logic and duplicate skipping

        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;

            // Early termination: if the smallest possible sum is > 0, no more triplets
            if (nums[i] > 0) break;

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

            while (left < right) {
                int sum = nums[left] + nums[right];

                if (sum == target) {
                    triplets.add(new int[]{nums[i], nums[left], nums[right]});

                    // Skip duplicates for left pointer
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    // Skip duplicates for right pointer
                    while (left < right && nums[right] == nums[right - 1]) right--;

                    left++;
                    right--;

                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }

        return triplets;
    }

    public static void main(String[] args) {
        int[] transactions = {-1, 0, 1, 2, -1, -4};

        List<int[]> results = findAllTripletsSummingToZero(transactions);

        System.out.println("Triplets summing to zero:");
        for (int[] triplet : results) {
            System.out.println("  [" + triplet[0] + ", " + triplet[1] + ", " + triplet[2] + "]");
        }
    }
}

package io.thecodeforge.algo;

public class FloydsCycleDetection {

    static class ListNode {
        int value;
        ListNode next;
        ListNode(int val) { this.value = val; }
    }

    /**
     * Detects if a linked list has a cycle using Floyd's algorithm.
     * Slow pointer: 1 step. Fast pointer: 2 steps.
     * If they meet, there is a cycle.
     * O(n) time, O(1) space.
     */
    public static boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

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

            if (slow == fast) {       // Pointers met — cycle exists
                return true;
            }
        }

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

    /**
     * Finds the node where the cycle begins.
     * After detecting the meeting point, reset one pointer to head.
     * Advance both one step at a time. They meet at the cycle entrance.
     */
    public static ListNode findCycleStart(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

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

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

        // Phase 2: find cycle entrance
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }

        return slow; // This is the cycle entrance
    }

    public static void main(String[] args) {
        // Build: 1 -> 2 -> 3 -> 4 -> 5 -> back to 3
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        n1.next = n2; n2.next = n3; n3.next = n4; n4.next = n5;
        n5.next = n3; // Cycle: 5 -> 3

        System.out.println("Has cycle: " + hasCycle(n1));
        ListNode cycleStart = findCycleStart(n1);
        System.out.println("Cycle starts at node with value: " + (cycleStart != null ? cycleStart.value : "none"));
    }
}

// io.thecodeforge — dsa tutorial

public class TwoSumSorted {
    public int[] findPair(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        
        while (left < right) {
            int currentSum = numbers[left] + numbers[right];
            
            if (currentSum == target) {
                return new int[]{left, right};
            }
            
            if (currentSum < target) {
                left++;
            } else {
                right--;
            }
        }
        
        return new int[]{-1, -1};
    }
}

// io.thecodeforge — dsa tutorial
// Warning: O(n²) — do not ship this

public class TwoSumBruteForce {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

// io.thecodeforge — dsa tutorial

public class TwoPointerProof {
    public static void main(String[] args) {
        int[] data = {1, 3, 5, 7, 9, 11, 13};
        int target = 16;
        int left = 0;
        int right = data.length - 1;
        int iterations = 0;
        
        while (left < right) {
            iterations++;
            int sum = data[left] + data[right];
            System.out.printf("Step %d: left=%d (%d), right=%d (%d), sum=%d%n",
                iterations, left, data[left], right, data[right], sum);
            
            if (sum == target) {
                System.out.printf("Found pair: (%d, %d)%n", data[left], data[right]);
                System.out.printf("Total iterations: %d (instead of %d)%n",
                    iterations, (data.length * (data.length - 1)) / 2);
                return;
            }
            
            if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        
        System.out.println("No pair found");
    }
}

// io.thecodeforge — dsa tutorial

// Merging two sorted server logs into one stream
public class MergeSortedLogs {
    public static void merge(long[] a, long[] b, long[] out) {
        int i = 0, j = 0, k = 0;
        while (i < a.length && j < b.length) {
            out[k++] = (a[i] <= b[j]) ? a[i++] : b[j++];
        }
        while (i < a.length) out[k++] = a[i++];
        while (j < b.length) out[k++] = b[j++];
    }

    public static void main(String[] args) {
        long[] s1 = {100, 203, 400};
        long[] s2 = {150, 250, 300};
        long[] result = new long[s1.length + s2.length];
        merge(s1, s2, result);
        for (long t : result) System.out.print(t + " ");
    }
}

// io.thecodeforge — dsa tutorial

// O(n²) code that died under load → rewritten with two pointers
public class ProductionFixExample {
    // BAD: nested loop checks all pairs
    static boolean hasPairSumBad(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++)
            for (int j = i + 1; j < arr.length; j++)
                if (arr[i] + arr[j] == target) return true;
        return false;
    }

    // GOOD: two pointers on sorted data
    static boolean hasPairSum(int[] arr, int target) {
        java.util.Arrays.sort(arr);
        int l = 0, r = arr.length - 1;
        while (l < r) {
            int sum = arr[l] + arr[r];
            if (sum == target) return true;
            else if (sum < target) l++;
            else r--;
        }
        return false;
    }

    public static void main(String[] args) {
        int[] data = {3, 5, 2, 8, 11};
        System.out.println(hasPairSum(data, 10));
    }
}