Two Pointer Bug: Unsorted Data Skips Valid Pairs

Every coding interview has a handful of patterns that show up again and again. Two pointers is one of the most common — and one of the most misunderstood. Candidates often brute-force their way through problems that a senior dev would knock out in O(n) time because they don't recognise the signal that two pointers is the right tool. Missing that signal doesn't just cost you efficiency points; it costs you the job.

The two pointer technique exists to eliminate the need for nested loops. Any time you find yourself writing a loop inside a loop to compare or relate two positions in the same collection, there's a good chance you're doing more work than you need to. Two pointers lets you move through the data from two positions simultaneously — either from opposite ends converging toward the middle, or from the same starting point racing at different speeds — and cut your time complexity from O(n²) down to O(n).

By the end of this article you'll be able to identify which of the three two-pointer variants to reach for (opposite ends, same direction, or fast-slow), implement the three most interview-common problems from scratch without hints, and explain your reasoning out loud — which is the part that actually gets you hired.

What Two Pointer Technique Actually Solves

The two-pointer technique uses two indices traversing a data structure to solve problems that would otherwise require nested loops. Instead of O(n²) brute force, you move pointers based on a condition — typically one pointer starts at each end, or both start at the beginning with one ahead. The core mechanic is that each pointer advances monotonically, never backtracking, which guarantees each element is visited at most once per pointer. This yields O(n) time and O(1) space for many array and string problems.

In practice, the technique works only when the data is sorted or when the problem has a monotonic property — like finding a pair that sums to a target in a sorted array. If the array is unsorted, moving pointers based on comparison operators (e.g., if sum < target, move left) is invalid because you cannot know whether a better pair lies ahead or behind. The pointer movement must be deterministic; any guess based on unsorted values will skip valid pairs.

Use two pointers when you need to find pairs, triplets, or subarrays that satisfy a condition in a sorted sequence, or when you need to reverse or partition in place. It is not a general-purpose optimization — it exploits order. In real systems, this pattern appears in merging sorted logs, detecting palindromes in user input, or finding the closest pair of points in a sorted list. Misapplying it to unsorted data is a common source of subtle bugs that pass unit tests but fail in production.

Why Two Pointers Beat Brute Force — The Core Intuition

Let's get the intuition rock solid before touching code. The brute-force approach to 'find two numbers that sum to a target' is to check every pair: index 0 with index 1, index 0 with index 2, and so on. That's n*(n-1)/2 comparisons — O(n²). It works, but it's slow and it signals to an interviewer that you haven't spotted the pattern.

The key insight is this: if your data is sorted, you already know something about every element's relationship to every other element without checking them all. If the number at the left pointer plus the number at the right pointer is too large, you don't need to check the right pointer against anything to its right — they'd all be even larger. So you move the right pointer one step inward. If the sum is too small, you move the left pointer one step inward. Each step eliminates an entire class of possibilities.

This is why two pointers almost always requires a sorted array for the opposite-ends variant. The sort itself costs O(n log n), but the pointer walk is O(n), so your overall complexity is O(n log n) — still far better than O(n²) for large inputs. When the input is already sorted, you get pure O(n).

Now here's a nuance most tutorials skip: the elimination trick only works because the array is monotonic. If you applied the same logic to an unsorted array, moving the left pointer when the sum is too small might actually skip the correct pair — because a larger value could be hiding to the left of the current left pointer. That's why sorting is non-negotiable for this variant.

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

Removing Duplicates In-Place — The Same-Direction Variant

Not every two-pointer problem has the pointers moving toward each other. The same-direction variant uses a slow pointer and a fast pointer both starting at the left — the fast pointer scouts ahead while the slow pointer marks where the next valid element should land.

This pattern is perfect for in-place array modification problems: removing duplicates, removing a specific value, or filtering elements without allocating a new array. The slow pointer essentially tracks 'the last confirmed valid position', and the fast pointer asks 'is this element worth keeping?'

Think of it like editing a manuscript. The fast-reading editor races through the draft, and every time they find a sentence worth keeping, they hand it to the slow typist who places it into the clean copy. The typist never skips ahead; the editor never looks back.

This approach runs in O(n) time and O(1) space — a big deal in interviews where the constraint 'do it in-place without extra memory' is explicitly stated. If you reach for a HashSet here, you've violated that constraint even though you'd get the right answer.

One subtlety: this variant requires that duplicates are adjacent, which is guaranteed when the array is sorted. For unsorted arrays, this slow/fast pattern won't remove all duplicates — only adjacent ones. If the input is unsorted, you either sort first (and the problem often allows it) or use a set.

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

Detecting a Cycle — The Fast-Slow (Floyd's) Variant

The third variant is the most elegant: the fast pointer moves two steps for every one step the slow pointer takes. If there's a cycle in a linked list, the fast pointer will eventually lap the slow pointer and they'll meet inside the cycle. If there's no cycle, the fast pointer will fall off the end of the list.

Why does this work? Think of two runners on a circular track — one running twice as fast as the other. They'll always meet eventually, no matter how long the track is. If the track is a straight road with a dead end, the faster runner hits the wall first and you know it's not circular.

This is Floyd's Cycle Detection algorithm. It's O(n) time and O(1) space — compare that to the HashSet approach, which is also O(n) time but O(n) space. In an interview, the follow-up 'can you do it without extra memory?' is almost guaranteed, and this is your answer.

This pattern extends beyond linked lists. It appears in problems about finding the duplicate number in an array, detecting infinite loops in graph traversal, and even in cryptography.

One common variation: after detecting the cycle, you can find the exact node where the cycle begins. Reset the slow pointer to head, then move both pointers one step at a time. The node where they meet is the start of the cycle. The proof involves the distance from head to cycle start being equal to the distance from the meeting point around the cycle back to the start.

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

Container With Most Water — Real Interview Walkthrough

This classic problem is a perfect test of opposite-ends two-pointer thinking. You're given an array of non-negative integers where each value represents the height of a vertical line at that index. You need to find two lines that together with the x-axis form a container that holds the most water.

The brute force checks every pair — O(n²). The two-pointer solution: start left at index 0 and right at the last index. The area is limited by the shorter line: area = min(height[left], height[right]) * (right - left). Move the pointer with the shorter line inward. Why? Because the only way to possibly get a larger area is to replace the limiting side. If you move the taller line, the width shrinks and the height can never exceed the shorter line — area can only stay the same or decrease.

This is the exact same elimination logic as two-sum: each move discards all pairs that would be worse than the current best. The algorithm runs in O(n) time and O(1) space. Here's the implementation in Java.

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

Three Sum Problem: Extending the Pattern to Multiple Pointers

The two-pointer pattern extends naturally to three-sum problems. The classic 'Given an array of integers, find all unique triplets that sum to zero' is a staple of coding interviews. The approach: sort the array, then fix one number at a time using a loop, and for the remaining range apply the two-sum two-pointer technique to find pairs that sum to -fixedNumber.

This gives O(n²) overall complexity — because the outer loop runs n times and the inner two-pointer walk is O(n). Without two pointers you'd be at O(n³).

The key challenge is handling duplicate values. After sorting, if you skip duplicate values for the fixed number, you avoid duplicate triplets. Similarly, inside the two-pointer walk, when you find a valid pair, move both pointers inward past any duplicate values before continuing.

This generalises to k-sum: fix k-2 numbers, then use two pointers on the remaining range. Complexity O(n^(k-1)).

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

String Palindromes: Two Pointers on Characters

Strings are arrays of characters, so two pointers work perfectly for palindrome checking. Start one pointer at index 0 and one at the last index. Compare characters, then move inward. If any pair doesn't match, it's not a palindrome.

This is O(n) time and O(1) space. A variant with character filtering (ignore non-alphanumeric, case-insensitive) is equally common — just advance pointers over invalid characters before comparing.

Two pointers also solve problems like 'reverse a string in-place' (swap characters from both ends) and 'valid palindrome II' (allow at most one deletion).

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

Easy Problems: Where You Prove You Can Walk Before You Run

Most interviewers don't start with Three Sum. They start with the easy variants to see if you understand pointer mechanics without the algorithmic overhead. These problems test whether you can spot when a single pass with two indices is enough — and they're embarrassingly common in phone screens.

Remove Duplicates from a Sorted Array? That's just a slow pointer tracking the write position and a fast pointer scanning for new values. Move Zeroes to End? Same pattern: slow pointer lands on the next non-zero slot, fast pointer finds the non-zero values. Two Sum on a sorted array? Classic opposite-direction pointers converging toward the target sum.

The trap here is overcomplicating. Juniors write hash maps for sorted arrays. They create temporary arrays when they should swap in-place. These problems exist to filter out candidates who reach for O(n²) brute force when O(n) is sitting right there.

Master these. They're the warm-up that separates engineers who "know of" two pointers from those who actually wield them.

// io.thecodeforge — interview tutorial

def move_zeroes(nums: list[int]) -> None:
    write_idx = 0
    for read_idx in range(len(nums)):
        if nums[read_idx] != 0:
            nums[write_idx], nums[read_idx] = nums[read_idx], nums[write_idx]
            write_idx += 1

# Example usage
arr = [0, 1, 0, 3, 12]
move_zeroes(arr)
print(arr)

Medium Problems: When You Need a Sorted Array and a Sharp Eye

Medium problems are where the interviewer stops holding your hand. The input isn't always sorted — but your success depends on making it so. Take 'Closest Pair Sum' or 'Count pairs with absolute difference equal to k'. The naive approach is O(n²) double loop. The two-pointer approach demands you sort first, then slide pointers.

Here's the pattern: sort the array, then initialize left at 0 and right at the end. Compute the current pair's sum. If it's too small, move left forward. If too large, move right backward. If you need a specific difference, adjust a single pointer until the gap matches. The sorting cost (O(n log n)) pays for itself by collapsing the inner loop.

The production reality? I've used this pattern to merge log files, reconcile financial transactions, and detect data drift between database snapshots. When you're comparing two sorted streams, two pointers are your cheapest option.

Don't just memorize the code. Understand why the sort is mandatory and why the pointers only move in one direction. That's what separates a solution from a guess.

// io.thecodeforge — interview tutorial

def closest_pair_sum(nums: list[int], target: int) -> tuple[int, int]:
    nums.sort()
    left, right = 0, len(nums) - 1
    closest_sum = float('inf')
    best_pair = None

    while left < right:
        current_sum = nums[left] + nums[right]
        if abs(current_sum - target) < abs(closest_sum - target):
            closest_sum = current_sum
            best_pair = (nums[left], nums[right])
        
        if current_sum < target:
            left += 1
        else:
            right -= 1
    
    return best_pair

print(closest_pair_sum([10, 22, 28, 29, 30, 40], 54))

Two Pointers on Sorted Arrays vs Unsorted Arrays

The two-pointer technique is often associated with sorted arrays, but its applicability extends to unsorted arrays under specific conditions. Understanding when sorting is required versus when it can be avoided is crucial for efficient problem-solving.

Sorted Arrays: Most classic two-pointer problems (e.g., two-sum II, three-sum, container with most water) rely on sorted input. Sorting enables the 'opposite direction' pattern where pointers start at ends and move inward based on comparison. For example, in the two-sum problem with a sorted array, if the sum of left and right pointers is less than target, we increment left; if greater, we decrement right. This works because sorting guarantees monotonicity.

Unsorted Arrays: Two pointers can still be used on unsorted arrays in the 'same direction' variant (e.g., removing duplicates in-place) or when the problem constraints allow O(n) time without sorting. For instance, in the 'move zeroes' problem, we use two pointers to partition the array without sorting. However, for problems requiring comparisons like 'pair with given sum', unsorted arrays typically require a hash map for O(n) time, or sorting first (O(n log n)) then two pointers.

Key Insight: If the problem involves finding pairs/triplets with a specific property (sum, difference, etc.), sorting is usually necessary for the two-pointer approach to work. If the problem involves in-place rearrangement or partitioning, sorting may not be needed.

Example: Given an unsorted array [3, 1, 4, 2] and target sum 5, a two-pointer approach on the sorted array [1,2,3,4] works: pointers at 1 and 4 sum to 5. Without sorting, you'd need a hash map.

Edge Case: If the array contains duplicates and you need unique pairs, sorting helps skip duplicates easily.

Conclusion: Always assess whether sorting is acceptable given time constraints. If O(n log n) is acceptable, sorting enables the powerful two-pointer pattern. If not, consider hash maps or other techniques.

# Sorted array two-sum (two pointers)
def two_sum_sorted(nums, target):
    nums.sort()
    left, right = 0, len(nums)-1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [nums[left], nums[right]]
        elif s < target:
            left += 1
        else:
            right -= 1
    return []

# Unsorted array two-sum (hash map)
def two_sum_unsorted(nums, target):
    seen = {}
    for num in nums:
        complement = target - num
        if complement in seen:
            return [complement, num]
        seen[num] = True
    return []

Three Sum, Four Sum: Generalizing the K-Sum Pattern

The k-sum problem (finding k numbers that sum to a target) is a classic extension of the two-pointer technique. The pattern generalizes: for k > 2, we fix one number and recursively solve (k-1)-sum on the remaining subarray. The base case is two-sum using two pointers on a sorted array.

Three Sum (k=3): Given an array, find all unique triplets that sum to zero. Steps: 1) Sort the array. 2) Iterate i from 0 to n-3. For each i, use two pointers (left = i+1, right = n-1) to find pairs that sum to -nums[i]. Skip duplicates by checking adjacent elements. Time complexity: O(n^2).

Four Sum (k=4): Similar, but we fix two numbers (i and j) and then two-sum on the remaining. Time complexity: O(n^3). To avoid duplicates, skip identical values for i and j.

General K-Sum: Recursive approach: function kSum(nums, target, k, start). If k == 2, use two pointers. Else, iterate from start to len(nums)-k, fix nums[i], and call kSum with target - nums[i], k-1, i+1. Skip duplicates at each level.

Optimization: Early termination: if smallest possible sum > target or largest possible sum < target, break.

Example: For three sum with nums = [-1,0,1,2,-1,-4], sorted = [-4,-1,-1,0,1,2]. i=-4: two-sum for 4? none. i=-1: two-sum for 1? pairs (0,1) and (-1,2) but skip duplicate -1. Result: [[-1,-1,2],[-1,0,1]].

Edge Cases: Duplicates must be skipped to avoid duplicate triplets. Also, handle large k carefully due to combinatorial explosion.

Conclusion: The k-sum pattern demonstrates the power of reducing a problem to smaller subproblems using two pointers. It's a common interview topic that tests both recursion and pointer manipulation.

def kSum(nums, target, k):
    nums.sort()
    results = []
    
    def k_sum_recursive(start, target, k, path):
        if k == 2:
            left, right = start, len(nums)-1
            while left < right:
                s = nums[left] + nums[right]
                if s == target:
                    results.append(path + [nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left-1]:
                        left += 1
                    while left < right and nums[right] == nums[right+1]:
                        right -= 1
                elif s < target:
                    left += 1
                else:
                    right -= 1
        else:
            for i in range(start, len(nums)-k+1):
                if i > start and nums[i] == nums[i-1]:
                    continue
                # Early termination
                if nums[i] + (k-1)*nums[i+1] > target:
                    break
                if nums[i] + (k-1)*nums[-1] < target:
                    continue
                k_sum_recursive(i+1, target-nums[i], k-1, path+[nums[i]])
    
    k_sum_recursive(0, target, k, [])
    return results

# Example usage:
print(kSum([-1,0,1,2,-1,-4], 0, 3))  # Three sum

Two Pointers with Hash Map for O(n) Solutions

Combining two pointers with a hash map can yield O(n) solutions for problems that typically require sorting. This hybrid approach is useful when you need to find pairs or subarrays with a given property without altering the original order.

Concept: Use a hash map to store seen elements or their indices. Then, use two pointers (often one fast, one slow) to traverse the array while consulting the hash map for O(1) lookups.

Example 1: Two Sum (Unsorted) The classic two-sum problem can be solved with a single pass: iterate with pointer i, check if target - nums[i] is in the hash map. If yes, return pair. Else, add nums[i] to map. This is essentially a two-pointer (one pointer i, the other is implicit via map) but achieves O(n) time and O(n) space.

Example 2: Longest Substring Without Repeating Characters Use two pointers (left and right) to maintain a sliding window, and a hash map to store the last index of each character. When a repeat is found, move left to max(left, last_index+1). This is O(n) time.

Example 3: Subarray Sum Equals K Use a hash map to store cumulative sums and their frequencies. Two pointers are not directly used, but the technique of prefix sum with hash map is analogous to two-pointer thinking: one pointer iterates, the other is the map lookup.

When to Use: When the problem requires O(n) time and the array is unsorted, or when you need to track frequencies/indices of elements. The hash map compensates for the lack of sorting.

Trade-offs: Extra O(n) space. However, it often simplifies code and avoids sorting overhead.

Example Code: Two sum with hash map and two-pointer style (one pointer i, map as the other 'pointer').

Edge Cases: Duplicates: in two-sum, if duplicates exist, the hash map approach still works if we store indices carefully.

Conclusion: Combining two pointers with a hash map is a powerful pattern for O(n) solutions, especially for unsorted arrays or sliding window problems.

# Two Sum using hash map (O(n))
def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

# Longest Substring Without Repeating Characters (sliding window + hash map)
def length_of_longest_substring(s):
    char_map = {}
    left = 0
    max_len = 0
    for right, ch in enumerate(s):
        if ch in char_map and char_map[ch] >= left:
            left = char_map[ch] + 1
        char_map[ch] = right
        max_len = max(max_len, right - left + 1)
    return max_len

# Example usage:
print(two_sum([2,7,11,15], 9))  # [0,1]
print(length_of_longest_substring("abcabcbb"))  # 3