Two Pointers Pattern - Dev Weekends

Pattern Recognition Cheatsheet (Read This First)

Reach for Two Pointers when the problem statement says…

Problem phrasing	Variant
”sorted array” + “find pair / two numbers that sum to X”	Converging (LC 167)
“find all unique triplets that sum to zero”	Sort + fix one + converge (LC 15)
“find all unique quadruplets that sum to target”	Sort + fix two + converge (LC 18)
“is the string a palindrome (ignoring punctuation)“	Converging from both ends (LC 125)
“container with most water” / “two lines forming max area”	Greedy converging (LC 11)
“trap rain water between bars”	Converging with running max (LC 42)
“remove duplicates from sorted array in-place”	Fast/slow (LC 26, LC 80)
“move all zeros to end / partition by parity”	Fast/slow (LC 283)
“sort array of 0s, 1s, 2s in-place”	Three pointers (Dutch flag, LC 75)
“merge two sorted arrays in-place into the first”	Reverse converging from end (LC 88)
“detect cycle / find middle of linked list”	Fast/slow (Floyd’s, LC 141, LC 876)
“squares of sorted array (with negatives)“	Converging, write from end (LC 977)
“valid palindrome after deleting at most one char”	Converging with branch (LC 680)
“reverse string / vowels / array in-place”	Converging swap (LC 344, LC 345)

Hard signal: the array is sorted (or you can sort), AND you need to find pairs / triplets / partitions, AND you want O(1) extra space. That is the Two Pointers calling card. If sorting is forbidden or destroys the answer, use HashMap instead.

What is Two Pointers?

The Two Pointers pattern uses two pointers to traverse an array or string, typically moving towards each other or in the same direction. It transforms O(n squared) brute force solutions into O(n) optimal ones.

Quick Recognition: If you see a sorted array + need to find pairs/triplets + want O(1) space, Two Pointers is likely the answer.

Canonical Template Code

This is the boilerplate. Memorize it. Then specialize for the problem.

# THE Two Pointers template (converging variant). Memorize this shape.
def two_pointers_converging(arr, target):
    # left starts at the smallest index, right at the largest -- gives us
    # control over the *sum* (or *area*, *length*, etc.) by moving inward
    left, right = 0, len(arr) - 1

    while left < right:                  # strict < because we never want left == right
                                          # (using the same index for both pointers is a bug
                                          #  for sum problems -- you would use one element twice)
        current = arr[left] + arr[right]  # the quantity we are optimizing / matching

        if current == target:
            return [left, right]          # found it -- return early
        elif current < target:
            left += 1                     # need a LARGER value; the smallest available is at left+1
        else:
            right -= 1                    # need a SMALLER value; the largest available is at right-1

    return [-1, -1]                      # exhausted all valid pairs without finding target


# THE Two Pointers template (fast/slow variant). For in-place rewrites.
def two_pointers_fast_slow(arr, predicate):
    # slow tracks the "write position" -- where the next valid element goes
    # fast scans through every element once
    slow = 0

    for fast in range(len(arr)):
        if predicate(arr[fast]):          # element passes the keep-it test
            arr[slow] = arr[fast]         # write it at the slow position
            slow += 1                     # advance write head only on a keep
                                           # (skipped elements get overwritten later)

    return slow                           # length of the kept prefix

// THE Two Pointers template (converging variant). Memorize this shape.
public int[] twoPointersConverging(int[] arr, int target) {
    // left starts at smallest index, right at largest -- so we can steer
    // the sum/area by moving the pointer that improves it
    int left = 0, right = arr.length - 1;

    while (left < right) {                 // strict <: same index would mean using one elem twice
        int current = arr[left] + arr[right]; // the quantity to compare against target

        if (current == target) {
            return new int[]{left, right}; // found
        } else if (current < target) {
            left++;                         // sum too small -> increase by moving left up (sorted)
        } else {
            right--;                        // sum too large -> decrease by moving right down
        }
    }
    return new int[]{-1, -1};
}

// THE Two Pointers template (fast/slow variant). For in-place rewrites.
public int twoPointersFastSlow(int[] arr, java.util.function.IntPredicate keep) {
    int slow = 0;                          // write position
    for (int fast = 0; fast < arr.length; fast++) {
        if (keep.test(arr[fast])) {
            arr[slow] = arr[fast];         // overwrite slow with kept element
            slow++;                         // slow advances only on keep -> compacted prefix
        }
    }
    return slow;
}

Pattern Recognition Checklist

Before using Two Pointers, ask yourself:

Use Two Pointers When

Array is sorted (or can be sorted)
Need to find pairs with a property
In-place modification required
Need to compare elements from ends
Want to avoid O(n²) nested loops

Don't Use When

Need to preserve original order
Array is unsorted and sorting changes answer
Need to find subarrays (use Sliding Window)
Need lookup by value (use HashMap)

When to Use

Sorted Arrays

Finding pairs, triplets, or elements with specific sum

Palindrome Problems

Checking or creating palindromes

Merging Arrays

Merging sorted arrays or linked lists

Removing Duplicates

In-place array modifications

Pattern Variations

1. Opposite Direction (Converging)

Pointers start at both ends and move towards the center.

def two_sum_sorted(arr, target):
    """Find two numbers in sorted array that sum to target"""
    left, right = 0, len(arr) - 1
    
    while left < right:
        current_sum = arr[left] + arr[right]
        
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1  # Need larger sum
        else:
            right -= 1  # Need smaller sum
    
    return [-1, -1]  # Not found

public int[] twoSumSorted(int[] arr, int target) {
    // Find two numbers in sorted array that sum to target
    int left = 0, right = arr.length - 1;
    
    while (left < right) {
        int currentSum = arr[left] + arr[right];
        
        if (currentSum == target) {
            return new int[]{left, right};
        } else if (currentSum < target) {
            left++;  // Need larger sum
        } else {
            right--;  // Need smaller sum
        }
    }
    
    return new int[]{-1, -1};  // Not found
}

vector<int> twoSumSorted(vector<int>& arr, int target) {
    // Find two numbers in sorted array that sum to target
    int left = 0, right = arr.size() - 1;
    
    while (left < right) {
        int currentSum = arr[left] + arr[right];
        
        if (currentSum == target) {
            return {left, right};
        } else if (currentSum < target) {
            left++;  // Need larger sum
        } else {
            right--;  // Need smaller sum
        }
    }
    
    return {-1, -1};  // Not found
}

2. Same Direction (Fast & Slow)

Both pointers move in the same direction at different speeds.

def remove_duplicates(arr):
    """Remove duplicates from sorted array in-place"""
    if not arr:
        return 0
    
    slow = 0  # Points to last unique element
    
    for fast in range(1, len(arr)):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
    
    return slow + 1  # Length of unique elements

public int removeDuplicates(int[] arr) {
    // Remove duplicates from sorted array in-place
    if (arr.length == 0) return 0;
    
    int slow = 0;  // Points to last unique element
    
    for (int fast = 1; fast < arr.length; fast++) {
        if (arr[fast] != arr[slow]) {
            slow++;
            arr[slow] = arr[fast];
        }
    }
    
    return slow + 1;  // Length of unique elements
}

int removeDuplicates(vector<int>& arr) {
    // Remove duplicates from sorted array in-place
    if (arr.empty()) return 0;
    
    int slow = 0;  // Points to last unique element
    
    for (int fast = 1; fast < arr.size(); fast++) {
        if (arr[fast] != arr[slow]) {
            slow++;
            arr[slow] = arr[fast];
        }
    }
    
    return slow + 1;  // Length of unique elements
}

3. Container With Most Water

def max_area(height):
    """Find two lines that form container with most water"""
    left, right = 0, len(height) - 1
    max_water = 0
    
    while left < right:
        width = right - left
        h = min(height[left], height[right])
        max_water = max(max_water, width * h)
        
        # Move the shorter line inward
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_water

public int maxArea(int[] height) {
    // Find two lines that form container with most water
    int left = 0, right = height.length - 1;
    int maxWater = 0;
    
    while (left < right) {
        int width = right - left;
        int h = Math.min(height[left], height[right]);
        maxWater = Math.max(maxWater, width * h);
        
        // Move the shorter line inward
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxWater;
}

int maxArea(vector<int>& height) {
    // Find two lines that form container with most water
    int left = 0, right = height.size() - 1;
    int maxWater = 0;
    
    while (left < right) {
        int width = right - left;
        int h = min(height[left], height[right]);
        maxWater = max(maxWater, width * h);
        
        // Move the shorter line inward
        if (height[left] < height[right]) {
            left++;
        } else {
            right--;
        }
    }
    
    return maxWater;
}

4. Valid Palindrome

def is_palindrome(s):
    """Check if string is palindrome (alphanumeric only)"""
    left, right = 0, len(s) - 1
    
    while left < right:
        # Skip non-alphanumeric characters
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        
        if s[left].lower() != s[right].lower():
            return False
        
        left += 1
        right -= 1
    
    return True

public boolean isPalindrome(String s) {
    // Check if string is palindrome (alphanumeric only)
    int left = 0, right = s.length() - 1;
    
    while (left < right) {
        // Skip non-alphanumeric characters
        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;
}

bool isPalindrome(string s) {
    // Check if string is palindrome (alphanumeric only)
    int left = 0, right = s.length() - 1;
    
    while (left < right) {
        // Skip non-alphanumeric characters
        while (left < right && !isalnum(s[left])) {
            left++;
        }
        while (left < right && !isalnum(s[right])) {
            right--;
        }
        
        if (tolower(s[left]) != tolower(s[right])) {
            return false;
        }
        
        left++;
        right--;
    }
    
    return true;
}

5. 3Sum

def three_sum(nums):
    """Find all unique triplets that sum to zero"""
    nums.sort()
    result = []
    
    for i in range(len(nums) - 2):
        # Skip duplicates for first element
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        
        left, right = i + 1, len(nums) - 1
        
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                # Skip duplicates
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    
    return result

public List<List<Integer>> threeSum(int[] nums) {
    // Find all unique triplets that sum to zero
    Arrays.sort(nums);
    List<List<Integer>> result = new ArrayList<>();
    
    for (int i = 0; i < nums.length - 2; i++) {
        // Skip duplicates for first element
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        int left = i + 1, right = nums.length - 1;
        
        while (left < right) {
            int total = nums[i] + nums[left] + nums[right];
            
            if (total == 0) {
                result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                // Skip duplicates
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            } else if (total < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return result;
}

vector<vector<int>> threeSum(vector<int>& nums) {
    // Find all unique triplets that sum to zero
    sort(nums.begin(), nums.end());
    vector<vector<int>> result;
    
    for (int i = 0; i < (int)nums.size() - 2; i++) {
        // Skip duplicates for first element
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        int left = i + 1, right = nums.size() - 1;
        
        while (left < right) {
            int total = nums[i] + nums[left] + nums[right];
            
            if (total == 0) {
                result.push_back({nums[i], nums[left], nums[right]});
                // Skip duplicates
                while (left < right && nums[left] == nums[left + 1]) left++;
                while (left < right && nums[right] == nums[right - 1]) right--;
                left++;
                right--;
            } else if (total < 0) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return result;
}

6. Trapping Rain Water

def trap(height):
    """Calculate trapped water between elevation bars"""
    if not height:
        return 0
    
    left, right = 0, len(height) - 1
    left_max, right_max = height[left], height[right]
    water = 0
    
    while left < right:
        if left_max < right_max:
            left += 1
            left_max = max(left_max, height[left])
            water += left_max - height[left]
        else:
            right -= 1
            right_max = max(right_max, height[right])
            water += right_max - height[right]
    
    return water

public int trap(int[] height) {
    // Calculate trapped water between elevation bars
    if (height.length == 0) return 0;
    
    int left = 0, right = height.length - 1;
    int leftMax = height[left], rightMax = height[right];
    int water = 0;
    
    while (left < right) {
        if (leftMax < rightMax) {
            left++;
            leftMax = Math.max(leftMax, height[left]);
            water += leftMax - height[left];
        } else {
            right--;
            rightMax = Math.max(rightMax, height[right]);
            water += rightMax - height[right];
        }
    }
    
    return water;
}

int trap(vector<int>& height) {
    // Calculate trapped water between elevation bars
    if (height.empty()) return 0;
    
    int left = 0, right = height.size() - 1;
    int leftMax = height[left], rightMax = height[right];
    int water = 0;
    
    while (left < right) {
        if (leftMax < rightMax) {
            left++;
            leftMax = max(leftMax, height[left]);
            water += leftMax - height[left];
        } else {
            right--;
            rightMax = max(rightMax, height[right]);
            water += rightMax - height[right];
        }
    }
    
    return water;
}

7. Move Zeroes

def move_zeroes(nums):
    """Move all zeroes to end while maintaining order"""
    slow = 0  # Position for next non-zero element
    
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

public void moveZeroes(int[] nums) {
    // Move all zeroes to end while maintaining order
    int slow = 0;  // Position for next non-zero element
    
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            int temp = nums[slow];
            nums[slow] = nums[fast];
            nums[fast] = temp;
            slow++;
        }
    }
}

void moveZeroes(vector<int>& nums) {
    // Move all zeroes to end while maintaining order
    int slow = 0;  // Position for next non-zero element
    
    for (int fast = 0; fast < nums.size(); fast++) {
        if (nums[fast] != 0) {
            swap(nums[slow], nums[fast]);
            slow++;
        }
    }
}

8. Sort Colors (Dutch National Flag)

def sort_colors(nums):
    """Sort array of 0s, 1s, and 2s in-place"""
    low, mid, high = 0, 0, len(nums) - 1
    
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

public void sortColors(int[] nums) {
    // Sort array of 0s, 1s, and 2s in-place
    int low = 0, mid = 0, high = nums.length - 1;
    
    while (mid <= high) {
        if (nums[mid] == 0) {
            int temp = nums[low];
            nums[low] = nums[mid];
            nums[mid] = temp;
            low++;
            mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {  // nums[mid] == 2
            int temp = nums[mid];
            nums[mid] = nums[high];
            nums[high] = temp;
            high--;
        }
    }
}

void sortColors(vector<int>& nums) {
    // Sort array of 0s, 1s, and 2s in-place
    int low = 0, mid = 0, high = nums.size() - 1;
    
    while (mid <= high) {
        if (nums[mid] == 0) {
            swap(nums[low], nums[mid]);
            low++;
            mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else {  // nums[mid] == 2
            swap(nums[mid], nums[high]);
            high--;
        }
    }
}

Classic Problems

1. Two Sum II (Sorted Array)

Problem: Find two numbers in a sorted array that add up to target.Approach: Use converging pointers. If sum is too small, move left pointer right. If too large, move right pointer left.Time: O(n) | Space: O(1)

2. Container With Most Water

Problem: Find two lines that form a container holding the most water.Approach: Start from both ends. Move the pointer with the shorter line inward (greedy choice).Time: O(n) | Space: O(1)

3. Valid Palindrome

Problem: Check if a string is a palindrome (ignoring non-alphanumeric).Approach: Compare characters from both ends, skip non-alphanumeric.Time: O(n) | Space: O(1)

4. 3Sum

Problem: Find all unique triplets that sum to zero.Approach: Sort array, fix one element, use two pointers for remaining two.Time: O(n^2) | Space: O(1) excluding output

5. Trapping Rain Water

Problem: Calculate trapped water between elevation bars.Approach: Two pointers with max height tracking from both sides.Time: O(n) | Space: O(1)

Template Code

# Template 1: Converging Pointers
def converging_template(arr):
    left, right = 0, len(arr) - 1
    result = None
    
    while left < right:
        # Process current pair
        # Update result if needed
        
        if condition_move_left:
            left += 1
        else:
            right -= 1
    
    return result

# Template 2: Fast-Slow Pointers
def fast_slow_template(arr):
    slow = 0
    
    for fast in range(len(arr)):
        if some_condition(arr[fast]):
            arr[slow] = arr[fast]
            slow += 1
    
    return slow

// Template 1: Converging Pointers
public Object convergingTemplate(int[] arr) {
    int left = 0, right = arr.length - 1;
    Object result = null;
    
    while (left < right) {
        // Process current pair
        // Update result if needed
        
        if (conditionMoveLeft) {
            left++;
        } else {
            right--;
        }
    }
    
    return result;
}

// Template 2: Fast-Slow Pointers
public int fastSlowTemplate(int[] arr) {
    int slow = 0;
    
    for (int fast = 0; fast < arr.length; fast++) {
        if (someCondition(arr[fast])) {
            arr[slow] = arr[fast];
            slow++;
        }
    }
    
    return slow;
}

// Template 1: Converging Pointers
auto convergingTemplate(vector<int>& arr) {
    int left = 0, right = arr.size() - 1;
    
    while (left < right) {
        // Process current pair
        // Update result if needed
        
        if (conditionMoveLeft) {
            left++;
        } else {
            right--;
        }
    }
    
    return result;
}

// Template 2: Fast-Slow Pointers
int fastSlowTemplate(vector<int>& arr) {
    int slow = 0;
    
    for (int fast = 0; fast < arr.size(); fast++) {
        if (someCondition(arr[fast])) {
            arr[slow] = arr[fast];
            slow++;
        }
    }
    
    return slow;
}

Common Mistakes

Avoid These Pitfalls:

Off-by-one errors: Be careful with left < right vs left <= right
Infinite loops: Ensure pointers always move towards termination
Missing edge cases: Empty arrays, single elements, all duplicates
Modifying while iterating: Be careful when removing elements in-place

Debugging Checklist

When your Two Pointers solution fails, check:

Initialization

Are left and right starting at correct positions?

Loop Condition

Should it be left < right or left <= right?

Pointer Movement

Is at least one pointer moving in each iteration?

Edge Cases

Did you handle empty array, single element, all same elements?

Duplicates

Are you skipping duplicates correctly (for unique results)?

Complexity Quick Reference

Problem Type	Time	Space	Key Insight
Two Sum (sorted)	O(n)	O(1)	Move based on sum comparison
3Sum	O(n²)	O(1)	Fix one, two-pointer on rest
Remove Duplicates	O(n)	O(1)	Slow = write position
Container Water	O(n)	O(1)	Move shorter side inward
Trap Rain Water	O(n)	O(1)	Track max from both sides
Valid Palindrome	O(n)	O(1)	Skip non-alphanumeric

Interview Problems by Company

Easy
Medium
Hard

Problem	Company	Key Concept
Two Sum II	Amazon, Google	Basic converging
Valid Palindrome	Meta, Microsoft	Character comparison
Move Zeroes	Meta, Amazon	Fast-slow technique
Remove Duplicates	All FAANG	In-place modification
Squares of Sorted Array	Amazon	Converging with squares

Problem	Company	Key Concept
3Sum	All FAANG	Fix + two pointers
Container With Water	Amazon, Google	Greedy + converging
Sort Colors	Microsoft, Meta	Dutch flag (3 pointers)
3Sum Closest	Google, Meta	Tracking closest sum
Partition Labels	Amazon	Multiple passes

Problem	Company	Key Concept
Trapping Rain Water	Google, Amazon	Track max from both sides
4Sum	Google	Nested two pointers
Minimum Window Sort	Meta	Find unsorted subarray

Interview Tips

How to Explain Your Approach

Script for interviews:

“I notice the array is sorted, which suggests Two Pointers might work here.”
“I’ll use two pointers starting at opposite ends.”
“If the sum is too small, I move left pointer right to increase it.”
“If too large, I move right pointer left to decrease it.”
“This gives us O(n) time and O(1) space.”

When Interviewer Says...

Interviewer Says	You Should Think
”Can you do better than O(n²)?”	Two Pointers or HashMap
”Can you do it in O(1) space?”	Two Pointers (not HashMap)
“The array is sorted”	Definitely Two Pointers!
”Find a pair/triplet”	Two Pointers likely
”Modify array in-place”	Fast-slow pointers

Common Follow-ups

Be ready for these follow-ups:

“What if there are duplicates?” → Skip duplicates in loop
“What if no solution exists?” → Return appropriate default
“Can you handle negative numbers?” → Usually yes, same logic
“What if array is not sorted?” → Sort first, or use HashMap

Practice Problems

Problem	Difficulty	Link
Two Sum II	Easy	LeetCode 167
Valid Palindrome	Easy	LeetCode 125
3Sum	Medium	LeetCode 15
Container With Most Water	Medium	LeetCode 11
Trapping Rain Water	Hard	LeetCode 42

Practice Roadmap

Day 1: Basics

Solve: Two Sum II, Valid Palindrome
Focus: Understanding when to move which pointer

Day 2: Fast-Slow

Solve: Move Zeroes, Remove Duplicates
Focus: In-place modifications

Day 3: Multi-pointer

Solve: 3Sum, Sort Colors
Focus: Managing multiple pointers

Day 4: Advanced

Solve: Container With Water, Trapping Rain Water
Focus: Greedy decisions with pointers

Interview Tip: When you see a sorted array or need to find pairs/triplets, immediately consider Two Pointers before jumping to HashMap.

Worked LeetCode Problems

Five canonical problems. For each: signal that triggers Two Pointers, brute force first, optimized solution, and the bugs that fail edge cases.

LC 167 — Two Sum II (Input Array Is Sorted)

Problem. Given a 1-indexed sorted array of integers and a target, return the indices of two numbers that add up to the target. Exactly one solution exists. Pattern fit. “Sorted array” + “two numbers summing to target” — the textbook Two Pointers signal. Brute force. Two nested loops, O(n squared) time, O(1) space. Even though the array is sorted, brute force ignores that signal. Optimized with Two Pointers.

def twoSum(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        s = numbers[left] + numbers[right]
        if s == target:
            return [left + 1, right + 1]   # 1-indexed
        elif s < target:
            left += 1                       # need larger sum, advance left
        else:
            right -= 1                      # need smaller sum, retreat right
    return [-1, -1]

Why it works. Each step eliminates one row or column of the implicit pair matrix. We never miss the answer because moving inward on the wrong side would only worsen the sum direction. Complexity. O(n) time, O(1) space. Common bugs.

Forgetting 1-indexed return. LC 167 wants 1-indexed indices. Off-by-one fails 100% of test cases.
Using left <= right. Allows using the same element twice. Returns wrong pair when target == 2 * arr[i].

LC 15 — 3Sum

Problem. Given an integer array, find all unique triplets that sum to zero. Pattern fit. “All triplets summing to X” — fix one element, run Two Pointers on the rest. Brute force. Three nested loops, O(n cubed). Use a set of sorted tuples to dedupe — messy. Optimized.

def threeSum(nums):
    nums.sort()                             # required for both two-pointer scan AND dedupe
    result = []
    n = len(nums)

    for i in range(n - 2):
        if nums[i] > 0:
            break                            # all remaining are positive, sum cannot be zero
        if i > 0 and nums[i] == nums[i - 1]:
            continue                         # skip duplicate first elements

        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1                # skip duplicate seconds
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1               # skip duplicate thirds
                left += 1
                right -= 1
            elif total < 0:
                left += 1
            else:
                right -= 1
    return result

Complexity. O(n squared) time (sort dominated by inner scan), O(1) extra space ignoring output. Common bugs.

Skipping duplicates after recording, but only on one side. You must skip on both left and right, otherwise [-2, 0, 0, 2, 2] produces [[-2, 0, 2], [-2, 0, 2]].
Forgetting to break when nums[i] > 0. Not a correctness bug, but a 5x performance loss on large inputs with many positives.

LC 11 — Container With Most Water

Problem. Given an array of heights, find two lines that together with the x-axis form a container holding the most water. Pattern fit. “Pair from sorted-by-position array” + “maximize area” — greedy converging Two Pointers. Brute force. All pairs, O(n squared). Optimized.

def maxArea(height):
    left, right = 0, len(height) - 1
    best = 0
    while left < right:
        h = min(height[left], height[right])
        best = max(best, h * (right - left))
        # Move the SHORTER side -- moving the taller side cannot help
        # because the height is bounded by the shorter side regardless
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return best

Why moving the shorter side is correct. The area is bounded by the shorter line. Moving the taller side cannot increase the area (height is still bounded by the shorter side, and width decreases). Moving the shorter side at least gives a chance to find a taller pair. Complexity. O(n) time, O(1) space. Common bugs.

Moving the taller side. Misses the optimum on inputs like [1, 8, 6, 2, 5, 4, 8, 3, 7].
Updating area after moving pointers. Then you skip the current pair’s contribution. Always update before moving.

LC 125 — Valid Palindrome

Problem. Return true if string is a palindrome considering only alphanumeric characters and ignoring case. Pattern fit. “Palindrome check” — converging Two Pointers from both ends. Brute force. Build a filtered, lowercased string and compare with its reverse. O(n) time, O(n) space. Optimized.

def isPalindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1                            # skip non-alphanumeric on the left
        while left < right and not s[right].isalnum():
            right -= 1                           # skip non-alphanumeric on the right
        if s[left].lower() != s[right].lower():
            return False
        left += 1
        right -= 1
    return True

Complexity. O(n) time, O(1) space. Common bugs.

Forgetting left < right inside the inner skip loops. Causes index out-of-range when the entire string is non-alphanumeric, e.g., "....," or "...." (returning true is correct).
Comparing characters without .lower(). Fails on "A man, a plan, a canal: Panama".

LC 42 — Trapping Rain Water

Problem. Given an array of bar heights, compute the total water trapped after rain. Pattern fit. “Compute aggregate over array using boundaries from both sides” — converging Two Pointers with running maxes. Brute force. For each index, find max to left and max to right, take min, subtract bar height. O(n squared). Better but still not optimal. Precompute left-max and right-max arrays. O(n) time, O(n) space. Optimized (Two Pointers).

def trap(height):
    if not height:
        return 0
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    while left < right:
        if height[left] < height[right]:
            # left side is the bottleneck -- water at left is bounded by left_max
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            # right side is the bottleneck
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    return water

Why it works. When height[left] < height[right], we know the right side has at least one bar taller than left_max somewhere to the right. So water at left is determined purely by left_max (the right bound is already known to be at least as tall). Process the bottleneck side first. Complexity. O(n) time, O(1) space. Common bugs.

Initializing left_max = height[0] then accidentally double-counting position 0. Initialize to 0 and let the first comparison update it.
Comparing left_max against right_max instead of height[left] against height[right]. The decision is which current bar is shorter, not which max.

Caveats and Traps — Two Pointers

Using left <= right when you should use left < right. The <= allows the same index for both pointers, which means using one element twice. Catastrophic for sum problems where target = 2 * arr[i]. Use <= only when single-element processing is meaningful (Dutch flag, binary search variants).
Not sorting before applying converging pointers. Two Pointers requires monotonic order to make meaningful comparisons. On unsorted input, the pointer movement logic breaks because moving “right” on an unsorted array does not predictably increase or decrease anything.
Skipping duplicates only on one side in 3Sum. You must skip duplicate nums[left] AND duplicate nums[right] after recording a triplet. Otherwise [0, 0, 0, 0] outputs [0, 0, 0] multiple times.
Forgetting to update the result before moving pointers. In Container With Most Water, if you move pointers first and then update area, you miss the contribution of the current pair.
Using sort + Two Pointers on a problem that requires original indices. LC 1 (Two Sum, unsorted) wants original indices. Sorting destroys them unless you store (value, original_index) pairs. Use HashMap instead.
Confusing fast/slow with converging variants. Fast/slow rewrites in-place (LC 26, 283). Converging searches for pairs (LC 167, 15). They have different invariants — pick deliberately.
Off-by-one on the reverse merge (LC 88). Place pointers at m - 1, n - 1, m + n - 1. Forgetting to copy remaining nums2 elements after p1 finishes is the most common bug.
Trapping Rain Water with the wrong comparison. Compare height[left] to height[right], not left_max to right_max. The current-bar comparison is what tells you which side is the bottleneck.

Solutions and Patterns — Two Pointers Idioms

Always sort first unless the problem says “preserve order” or “indices required.” Sorting is O(n log n), often dominated by the O(n) or O(n squared) main scan — effectively free.
Use < for converging, <= for fast/slow inclusive scans. The mental check: “When left == right, is there meaningful work left?” If no, use <.
Skip duplicates by checking against the previous element. if i > 0 and nums[i] == nums[i-1]: continue is the canonical idiom in 3Sum / 4Sum.
For “fix-and-converge” patterns, wrap the converging two-pointer scan in an outer loop that fixes the first 1, 2, or k-2 elements. This generalizes 2Sum to kSum naturally.
For in-place modifications, the slow pointer always points to the next write position (not the current valid element). After the loop, slow is the new length.
For trapping rain water and similar, process the bottleneck side first. The side with the smaller current height is the binding constraint; you can compute its contribution without knowing the other side’s exact future.
For palindrome checks, wrap inner skip loops with while left < right and .... Otherwise inner loops can run past each other on degenerate inputs.
For merging from the end (LC 88), write from the back to avoid overwriting unread data. After the main loop, only nums2 leftovers need to be copied — nums1 leftovers are already in place.

Curated LeetCode Practice List

Group your practice by difficulty. Solve every Easy, then move to Medium. Hard problems are useful only after Easy and Medium feel mechanical.

Easy (start here, 5-8 problems)

LC #	Title	Variant tested
LC 167	Two Sum II - Input Array Is Sorted	Converging, classic baseline
LC 125	Valid Palindrome	Converging with skip logic
LC 344	Reverse String	Converging swap, in-place
LC 26	Remove Duplicates from Sorted Array	Fast/slow, in-place rewrite
LC 283	Move Zeroes	Fast/slow with swap to preserve order
LC 977	Squares of a Sorted Array	Converging, write to result from end
LC 88	Merge Sorted Array	Reverse converging, in-place from end
LC 392	Is Subsequence	Two pointers across two arrays

Medium (the meat of interview prep, 6-8 problems)

LC #	Title	Variant tested
LC 15	3Sum	Sort + fix-one + converging, dedupe
LC 16	3Sum Closest	Same as 3Sum but track closest sum
LC 11	Container With Most Water	Greedy converging on heights
LC 75	Sort Colors	Three pointers (Dutch flag)
LC 80	Remove Duplicates from Sorted Array II	Fast/slow with `slow - 2` trick
LC 18	4Sum	Fix-two + converging, generalizes 3Sum
LC 845	Longest Mountain in Array	Two pointers expanding from peaks
LC 1248	Count Subarrays with K Odd Numbers	Two-pointer + sliding (atMost trick)

Hard (after you have grinded the above, 5-6 problems)

LC #	Title	Variant tested
LC 42	Trapping Rain Water	Converging with running maxes
LC 4	Median of Two Sorted Arrays	Binary search disguised as two pointers
LC 76	Minimum Window Substring	Two pointers + frequency map (sliding window flavor)
LC 632	Smallest Range Covering K Lists	K pointers via min-heap
LC 581	Shortest Unsorted Continuous Subarray	Two passes from both ends
LC 1782	Count Pairs Of Nodes	Two pointers on sorted degree counts

Interview Questions

Deep-dive questions that test real understanding of the Two Pointers pattern, not just pattern matching. Expect interviewers to push past your initial answer.

Q1: Why does moving the shorter line inward work in Container With Most Water? Prove it doesn't skip the optimal answer.

Difficulty: SeniorWhat interviewers are really testing: Whether you understand the greedy correctness proof behind the pointer movement, not just that it works. This separates candidates who memorize solutions from those who can reason about algorithmic correctness and would be able to derive similar greedy strategies for novel problems.Strong answer:

The area is min(height[left], height[right]) * (right - left). When we move a pointer inward, the width always decreases by 1. The only way to get a larger area is if the height increases enough to compensate.
Suppose height[left] < height[right]. If we moved right inward instead, the new height is still capped by height[left] (since min(anything, height[left]) <= height[left]), AND the width decreased. So area strictly decreases or stays the same. We can safely discard all pairs involving current left with any right' < right.
This is essentially an elimination argument: by moving the shorter side, we only eliminate pairs that provably cannot beat the current best. We never skip a pair that could be optimal.
Complexity: O(n) time, O(1) space. Each pointer moves at most n times total.

# The key insight in code: we MUST move the shorter side
if height[left] < height[right]:
    left += 1   # All pairs (left, right'), right' < right are dominated
else:
    right -= 1  # All pairs (left', right), left' > left are dominated

Red flag answer: “You move the shorter one because a taller line might give more water.” This is hand-waving. If a candidate cannot articulate why no optimal pair is skipped, they memorized the pattern without understanding it. Another red flag: saying “it’s like binary search” — it is not, and that analogy breaks down immediately.Follow-ups:

What if there are many lines with the same height? Does the algorithm degenerate? What is the worst-case number of comparisons? (Answer: still O(n), each pointer moves at most n/2 times regardless of duplicates.)
Can you modify this to return ALL pairs of lines whose area is within 10% of the maximum? Does the two-pointer approach still work, or do you need a different strategy? (Answer: two-pointer no longer works cleanly because the elimination argument breaks — you would need to explore more pairs, potentially O(n^2) in the worst case, or use a sorted/stack-based approach.)

Q2: Given an unsorted array of integers, find if there exist two elements whose sum equals a target. What approach do you use and why?

Difficulty: Foundational (but the trap is the real test)What interviewers are really testing: Whether you blindly apply two pointers to every “find a pair” problem, or whether you recognize when a HashMap is the better tool. This is a pattern-recognition trap — strong candidates explain the trade-off; weak candidates force two pointers.Strong answer:

For an unsorted array, the right answer is a HashMap/HashSet, not two pointers. Insert each element and check if target - current exists. O(n) time, O(n) space.
Two pointers requires sorting first, which is O(n log n) and also destroys original indices — if the problem asks for indices (like LeetCode Two Sum), you lose that information unless you store original indices separately.
The trade-off: HashMap gives O(n) time but O(n) space. Sorting + two pointers gives O(n log n) time but O(1) space (if you do not need indices). Choose based on constraints.
In an interview, I would state: “Since the array is unsorted and we need O(n) time, I will use a HashMap. If the interviewer constrains me to O(1) space and does not need original indices, I would sort then use two pointers.”

# HashMap approach for unsorted arrays
def two_sum_unsorted(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return [-1, -1]

Red flag answer: Immediately jumping to “sort the array and use two pointers” without considering that sorting is O(n log n) and destroys index information. Or even worse: not knowing that two pointers requires a sorted input at all.Follow-ups:

What if memory is extremely constrained (embedded system, 2MB RAM) but the array has 100 million elements on disk? Now sorting + two pointers (external sort) might beat the HashMap approach. Walk me through that trade-off.
What if there are many duplicate values? Does the HashMap approach need modification? (Answer: depends on whether you need all pairs or just one. For all pairs, you need to store counts or lists of indices.)

Q3: In the 3Sum problem, why do we sort the array first? What breaks if we skip sorting?

Difficulty: IntermediateWhat interviewers are really testing: Whether you understand that sorting is not an arbitrary choice but a structural prerequisite that enables both the two-pointer scan and duplicate elimination. Also tests whether you can reason about alternatives and their costs.Strong answer:

Sorting serves two critical purposes in 3Sum:
1. Enables two-pointer scanning: After fixing one element, the remaining subarray is sorted, so converging pointers can systematically search in O(n) instead of O(n^2).
2. Makes duplicate skipping trivial: In a sorted array, duplicates are adjacent. You just check if nums[i] == nums[i-1]: continue. Without sorting, you would need a HashSet to track which triplets you have already seen, which is messier and uses O(k) extra space for k results.
Without sorting, you would need a HashMap-based approach: for each pair (i, j), check if -(nums[i] + nums[j]) exists. This is O(n^2) time (same as sorted approach) but requires O(n) extra space for the map and a set of sorted tuples to deduplicate results, which is error-prone.
The sorting cost is O(n log n), and the two-pointer scan is O(n^2), so sorting does not change the overall O(n^2) complexity. It is essentially “free.”

# Without sorting, duplicate handling becomes a nightmare:
# You would need something like:
seen_triplets = set()
for i in range(n):
    complement_map = {}
    for j in range(i + 1, n):
        comp = -(nums[i] + nums[j])
        if comp in complement_map:
            triplet = tuple(sorted([nums[i], nums[j], comp]))
            seen_triplets.add(triplet)
        complement_map[nums[j]] = j
# Messy, harder to get right, same time complexity

Red flag answer: “We sort because two pointers needs a sorted array” without explaining WHY two pointers needs sorted input or mentioning the duplicate-skipping benefit. Another red flag: not realizing the sorting cost is dominated by the O(n^2) scan.Follow-ups:

If the problem changes to 4Sum, how does the complexity change? Can you still use two pointers? (Answer: yes, fix two elements O(n^2), two-pointer scan O(n) for each = O(n^3) total. The pattern generalizes: k-Sum is O(n^(k-1)) with sorting + two pointers.)
What if the array is already sorted and has 10 million elements? What practical optimizations would you add? (Answer: early termination — if nums[i] > 0, no triplet starting here can sum to zero. If nums[i] + nums[i+1] + nums[i+2] > 0, break. These prune aggressively.)

Q4: Explain the difference between `left < right` and `left <= right` as loop conditions. When does picking the wrong one cause bugs?

Difficulty: FoundationalWhat interviewers are really testing: Attention to off-by-one errors, which are the #1 source of bugs in pointer-based code. This also reveals whether a candidate tests their code mentally with small inputs or just writes and hopes.Strong answer:

left < right means the pointers must have at least one element between them or be adjacent. When left == right, the loop exits. Use this when you are comparing/processing pairs of distinct elements (e.g., Two Sum, palindrome check, Container With Most Water).
left <= right means even when both pointers point to the same element, you still process it. Use this when a single element might still need processing (e.g., Dutch National Flag / Sort Colors, binary search).
Concrete bug example: In the palindrome check, using left <= right would not cause a bug (checking a single middle character against itself is fine), but in Two Sum, using left <= right could cause you to use the same element twice — returning [i, i] as a valid pair when arr[i] * 2 == target.
The mental model I use: Ask yourself: “When left == right, is there still meaningful work to do, or have I already considered everything?” If the answer is no, use <. If yes, use <=.

# Two Sum: left < right (never use same element twice)
while left < right:
    if arr[left] + arr[right] == target:
        return [left, right]

# Dutch Flag: mid <= high (single element still needs classification)
while mid <= high:
    if nums[mid] == 0:
        swap(nums, low, mid)
        low += 1
        mid += 1

Red flag answer: “I always use left < right for two pointers.” This shows the candidate does not think about why, just memorizes. Another red flag: being unable to produce a concrete input where the wrong condition causes a failure.Follow-ups:

In binary search, when do you use left < right vs left <= right vs left + 1 < right? What bug does each variant prevent? (Tests whether the candidate connects two-pointer reasoning to binary search, which is fundamentally a two-pointer technique.)
Walk me through what happens with the input [1, 2, 3, 4, 5] and target 6 using Two Sum with left <= right. Where exactly does it break? (Answer: when left = right = 2, it would return [2, 2] claiming 3 + 3 = 6, but you cannot use the same element twice.)

Q5: How does the two-pointer solution for Trapping Rain Water work, and why is it correct? What alternatives exist and when would you prefer them?

Difficulty: SeniorWhat interviewers are really testing: Deep understanding of a Hard-level problem with multiple valid approaches. The interviewer wants to see if you can explain the invariant that makes the two-pointer version work, and whether you have the judgment to discuss trade-offs between approaches.Strong answer:

Core invariant: At any position, the water trapped equals min(max_left, max_right) - height[i]. The two-pointer approach works because we always process from the side with the smaller known maximum. If left_max < right_max, we know the water at left is determined by left_max regardless of what lies between the pointers (since right_max is already larger, and anything in between could only increase the right maximum further).
Why it is correct: We process the “bottleneck side” first. When left_max < right_max, the constraining factor at position left is left_max, not right_max. So we can safely compute water at left without knowing the exact right_max — we just know it is at least as large.
Three approaches compared:

Approach	Time	Space	When to prefer
Prefix/suffix max arrays	O(n)	O(n)	Easiest to understand and code correctly in an interview. Good default.
Two pointers	O(n)	O(1)	When the interviewer explicitly asks for O(1) space or you are confident in the invariant.
Monotonic stack	O(n)	O(n)	When the problem is framed as “horizontal layers” or you need to process bars left-to-right only (streaming).

My interview strategy: I would start by explaining the prefix/suffix approach (simpler, harder to get wrong), then optimize to two pointers if asked for O(1) space.

# Two-pointer: process the bottleneck side first
while left < right:
    if left_max < right_max:
        left += 1
        left_max = max(left_max, height[left])
        water += left_max - height[left]  # safe: right_max >= left_max
    else:
        right -= 1
        right_max = max(right_max, height[right])
        water += right_max - height[right]  # safe: left_max >= right_max

Red flag answer: Jumping straight to the two-pointer solution without being able to explain the invariant. If a candidate says “we track the max from both sides and add the difference” but cannot explain WHY processing the smaller-max side first is valid, they memorized the code. Also a red flag: not knowing the prefix array approach exists.Follow-ups:

What if this is a 2D grid instead of 1D bars (LC 407 — Trapping Rain Water II)? Does two-pointer generalize? (Answer: no. You need a priority queue / BFS approach processing the boundary inward. The 1D invariant does not extend to 2D because water can escape in multiple directions.)
If the input is a stream of heights arriving one at a time and you need a running total of trapped water, which approach adapts best? (Answer: the monotonic stack approach adapts most naturally to streaming, since it processes left-to-right. Two pointers requires the full array upfront.)

Q6: Given a string, find the length of the longest substring without repeating characters. Is two pointers the right approach?

Difficulty: Intermediate (pattern misidentification trap)What interviewers are really testing: Whether the candidate distinguishes between two pointers and sliding window — they are related but not identical. This problem is sliding window, not classic two pointers. Candidates who lump them together reveal shallow pattern understanding.Strong answer:

This is a sliding window problem, not a classic two-pointer problem. The distinction matters:
- Two pointers typically work on sorted data or compare elements at both ends. Pointer movement is driven by comparison logic (sum too big/small, palindrome match/mismatch).
- Sliding window maintains a window with an invariant (in this case, “no repeating characters”) and expands/shrinks to maintain it. Pointer movement is driven by window validity.
The approach: expand the right pointer to grow the window. When a duplicate is found, shrink from the left until the window is valid again. Use a HashSet or HashMap to track characters in the current window.
Complexity: O(n) time (each character is added and removed from the set at most once), O(min(n, alphabet_size)) space.

def length_of_longest_substring(s):
    char_index = {}
    left = 0
    max_length = 0

    for right in range(len(s)):
        if s[right] in char_index and char_index[s[right]] >= left:
            left = char_index[s[right]] + 1
        char_index[s[right]] = right
        max_length = max(max_length, right - left + 1)

    return max_length

Red flag answer: “I would use two pointers starting from both ends” — this is completely wrong for this problem since you need to scan left-to-right maintaining a window. Another red flag: calling it “two pointers” without distinguishing the sliding window invariant. If a candidate cannot explain why converging pointers would fail here, they do not understand either pattern deeply enough.Follow-ups:

What if instead of “no repeating characters” the constraint is “at most K distinct characters”? How does your approach change? (Answer: same sliding window, but the HashMap tracks character counts. Shrink when distinct count exceeds K.)
Can you solve this with O(1) space if the input is guaranteed to be lowercase English letters only? (Answer: yes, use a fixed-size array of 26 instead of a HashMap. Space is O(1) since it does not grow with input size.)

Q7: You have a sorted array with duplicates. Remove duplicates in-place so each element appears at most twice. How does this change the fast-slow pointer approach?

Difficulty: IntermediateWhat interviewers are really testing: Whether the candidate can adapt a known template to a modified constraint, rather than only solving the exact problem they memorized. This is LC 80 (Remove Duplicates II) and tests flexible thinking with the fast-slow pattern.Strong answer:

The standard remove-duplicates uses slow to track the write position and skips when arr[fast] == arr[slow]. For “at most twice,” we need to compare arr[fast] against arr[slow - 1] (two positions back) instead of arr[slow].
Key insight: If arr[fast] == arr[slow - 1], we already have two copies of this value, so skip. Otherwise, write it.
Generalization: For “at most K duplicates,” compare arr[fast] against arr[slow - (K-1)]. This is a clean generalization that interviewers love.
Complexity: O(n) time, O(1) space. Single pass.

def remove_duplicates_at_most_twice(nums):
    if len(nums) <= 2:
        return len(nums)

    slow = 2  # First two elements are always valid

    for fast in range(2, len(nums)):
        if nums[fast] != nums[slow - 2]:
            nums[slow] = nums[fast]
            slow += 1

    return slow

# Generalized for at most K duplicates:
def remove_duplicates_at_most_k(nums, k):
    if len(nums) <= k:
        return len(nums)
    slow = k
    for fast in range(k, len(nums)):
        if nums[fast] != nums[slow - k]:
            nums[slow] = nums[fast]
            slow += 1
    return slow

Red flag answer: Using a counter variable to track how many times the current element has appeared. While this works, it is more complex and error-prone than the slow - 2 comparison trick. An even worse red flag: not realizing the array must be sorted for this approach to work, or wanting to use extra space.Follow-ups:

What if the array is not sorted? Can you still remove elements appearing more than twice in O(n) time? (Answer: you need a HashMap to count frequencies, then a second pass to filter. O(n) time but O(n) space. Two pointers alone cannot solve this on unsorted input.)
The interviewer says: “Now do it where each element appears at most K times, and K is a parameter.” Write it generalized. (Answer: shown above. Tests whether the candidate can abstract a pattern into a parameter.)

Q8: Given an array of n integers and a target, find the number of unique quadruplets that sum to the target. What is the best approach?

Difficulty: SeniorWhat interviewers are really testing: Whether the candidate can extend the two-pointer pattern to higher dimensions (4Sum), reason about time complexity of nested approaches, and apply pruning optimizations that show real problem-solving maturity.Strong answer:

Approach: Sort the array. Use two nested loops to fix the first two elements. For the remaining two, use converging two pointers. This gives O(n^3) time.
Duplicate handling: Skip duplicates at each level — for the first loop, second loop, and within the two-pointer scan. Same logic as 3Sum but applied at more levels.
Critical pruning optimizations (what separates good from great):
1. Early termination (too small): If nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target, break the outer loop — all remaining sums are larger.
2. Early termination (too large): If nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target, skip this i — even the largest possible sum with this i is too small.
3. Same pruning applies at the second loop level.
Complexity: O(n^3) time worst case, O(1) space (excluding output). With pruning, practical performance is much better.
Why not HashMap? You could use a HashMap of pair sums for O(n^2) time, but handling duplicates becomes extremely messy and the space is O(n^2). For an interview, the sorted + nested two-pointer approach is cleaner and safer to implement.

def four_sum(nums, target):
    nums.sort()
    n = len(nums)
    result = []

    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        # Pruning
        if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:
            break
        if nums[i] + nums[n-3] + nums[n-2] + nums[n-1] < target:
            continue

        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue
            left, right = j + 1, n - 1
            while left < right:
                total = nums[i] + nums[j] + nums[left] + nums[right]
                if total == target:
                    result.append([nums[i], nums[j], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif total < target:
                    left += 1
                else:
                    right -= 1
    return result

Red flag answer: Not being able to articulate the time complexity (saying O(n^2) because “two pointers is O(n)”). The correct reasoning: two outer loops O(n^2) times the two-pointer scan O(n) = O(n^3). Another red flag: implementing it without any pruning, then being unable to suggest optimizations when prompted.Follow-ups:

What is the general time complexity for K-Sum using this approach? (Answer: O(n^(K-1)). You nest K-2 loops and use two pointers for the innermost pair.)
For very large arrays where O(n^3) is too slow, can you think of a meet-in-the-middle approach? What is its complexity? (Answer: compute all pair sums in O(n^2), sort them, then use two pointers on the pair-sum array to find complementary pairs. Time is O(n^2 log n), but duplicate handling and reconstructing original indices is tricky.)

Q9: Given an unsorted array, find the shortest subarray that, if sorted, would make the entire array sorted. Which technique applies?

Difficulty: SeniorWhat interviewers are really testing: Whether the candidate can apply two pointers in a non-obvious setting. This is not the classic sorted-array two-pointer usage — it requires finding boundaries from both ends using a monotonicity invariant. Tests creative application of the pattern beyond textbook scenarios.Strong answer:

Approach: Use two pointers, but not the classic converging pair. Scan from the left to find the rightmost element that is “out of order” (smaller than some element to its left). Scan from the right to find the leftmost element that is “out of order” (larger than some element to its right).
Detailed steps:
1. Traverse left to right, tracking the running maximum. Whenever nums[i] < max_so_far, this position needs to be inside the sorted subarray. Track the rightmost such position as right_bound.
2. Traverse right to left, tracking the running minimum. Whenever nums[i] > min_so_far, this position needs to be inside the sorted subarray. Track the leftmost such position as left_bound.
3. The answer is right_bound - left_bound + 1. If no such bounds exist, the array is already sorted (return 0).
Why this works: Any element that violates the monotonicity when scanning from either end MUST be included in the subarray that needs sorting.
Complexity: O(n) time, O(1) space. Two passes.

def find_unsorted_subarray(nums):
    n = len(nums)
    max_seen, min_seen = float('-inf'), float('inf')
    right_bound, left_bound = -1, -1

    # Left to right: find rightmost element out of place
    for i in range(n):
        if nums[i] < max_seen:
            right_bound = i
        max_seen = max(max_seen, nums[i])

    # Right to left: find leftmost element out of place
    for i in range(n - 1, -1, -1):
        if nums[i] > min_seen:
            left_bound = i
        min_seen = min(min_seen, nums[i])

    if right_bound == -1:
        return 0  # Already sorted
    return right_bound - left_bound + 1

Red flag answer: “Sort the array and compare with the original to find the first and last mismatched positions.” While this gives the correct answer, it is O(n log n) time and O(n) space. If a candidate cannot improve beyond this, they do not understand how to use pointer-based scanning. Another red flag: trying to use converging two pointers from both ends simultaneously, which does not work here because the “out of place” boundaries are not symmetric.Follow-ups:

Can you prove that sorting just this subarray is sufficient? What if an element outside the subarray is affected? (Answer: by construction, all elements left of left_bound are smaller than everything in the subarray and already sorted, and all elements right of right_bound are larger and already sorted. So sorting the subarray restores global order.)
How would you adapt this if the requirement changes to “find the shortest subarray to REVERSE (not sort) to make the array sorted”? (Answer: much harder. The subarray to reverse must form a decreasing sequence that, when flipped, creates a valid sorted array. This requires checking that the reversed subarray merges correctly with both ends.)

Q10: You need to merge two sorted arrays into the first array which has enough trailing space. The naive approach copies to a new array. Can you do better?

Difficulty: Foundational (but the insight is the real test)What interviewers are really testing: Whether the candidate recognizes that starting from the end (reverse two-pointer) avoids overwriting elements that have not been processed yet. This is LC 88 (Merge Sorted Array) and is a classic interview warm-up that reveals whether a candidate truly understands pointer mechanics or just memorizes forward-scanning patterns.Strong answer:

The key insight: If you merge from the front, you overwrite elements in nums1 that you still need. By merging from the back (placing the largest elements first), you fill the trailing empty space and never overwrite unprocessed elements.
Use three pointers: p1 at the last real element of nums1, p2 at the last element of nums2, and write at the very end of nums1. Compare nums1[p1] and nums2[p2], place the larger one at write, and decrement.
Edge case: If p2 finishes first, nums1’s remaining elements are already in place. If p1 finishes first, copy the rest of nums2. The second case is the one most candidates forget.
Complexity: O(m + n) time, O(1) space. Truly in-place.

def merge(nums1, m, nums2, n):
    p1, p2, write = m - 1, n - 1, m + n - 1

    while p1 >= 0 and p2 >= 0:
        if nums1[p1] >= nums2[p2]:
            nums1[write] = nums1[p1]
            p1 -= 1
        else:
            nums1[write] = nums2[p2]
            p2 -= 1
        write -= 1

    # If nums2 has remaining elements, copy them
    while p2 >= 0:
        nums1[write] = nums2[p2]
        p2 -= 1
        write -= 1
    # No need to handle remaining nums1 -- already in place

Red flag answer: “Create a temporary array, merge into it, copy back.” This works but uses O(m + n) space and shows the candidate did not consider the reverse-direction insight. Also a red flag: writing the forward merge and not realizing it overwrites needed data until the interviewer points it out.Follow-ups:

Why do we not need to handle the case where p1 still has elements remaining? (Answer: those elements are already in their correct positions in nums1. Since we are writing from the back and nums1 is sorted, any remaining nums1 elements are the smallest and are already at the front.)
What if instead of two sorted arrays, you had K sorted arrays and needed to merge them all? Does the two-pointer approach scale, or do you need a fundamentally different technique? (Answer: for K arrays, use a min-heap / priority queue of size K. Two pointers does not generalize to K-way merge efficiently — pairwise merging would be O(nK) vs O(n log K) with a heap.)

​Pattern Recognition Cheatsheet (Read This First)

​What is Two Pointers?

​Canonical Template Code

​Pattern Recognition Checklist

Use Two Pointers When

Don't Use When

​When to Use

Sorted Arrays

Palindrome Problems

Merging Arrays

Removing Duplicates

​Pattern Variations

​1. Opposite Direction (Converging)

​2. Same Direction (Fast & Slow)

​3. Container With Most Water

​4. Valid Palindrome

​5. 3Sum

​6. Trapping Rain Water

​7. Move Zeroes

​8. Sort Colors (Dutch National Flag)

​Classic Problems

​Template Code

​Common Mistakes

​Debugging Checklist

​Complexity Quick Reference

​Interview Problems by Company

​Interview Tips

​Practice Problems

​Practice Roadmap

​Worked LeetCode Problems

​LC 167 — Two Sum II (Input Array Is Sorted)

​LC 15 — 3Sum

​LC 11 — Container With Most Water

​LC 125 — Valid Palindrome

​LC 42 — Trapping Rain Water

​Curated LeetCode Practice List

​Easy (start here, 5-8 problems)

​Medium (the meat of interview prep, 6-8 problems)

​Hard (after you have grinded the above, 5-6 problems)

​Interview Questions

Pattern Recognition Cheatsheet (Read This First)

What is Two Pointers?

Canonical Template Code

Pattern Recognition Checklist

When to Use

Pattern Variations

1. Opposite Direction (Converging)

2. Same Direction (Fast & Slow)

3. Container With Most Water

4. Valid Palindrome

5. 3Sum

6. Trapping Rain Water

7. Move Zeroes

8. Sort Colors (Dutch National Flag)

Classic Problems

Template Code

Common Mistakes

Debugging Checklist

Complexity Quick Reference

Interview Problems by Company

Interview Tips

Practice Problems

Practice Roadmap

Worked LeetCode Problems

LC 167 — Two Sum II (Input Array Is Sorted)

LC 15 — 3Sum

LC 11 — Container With Most Water

LC 125 — Valid Palindrome

LC 42 — Trapping Rain Water

Curated LeetCode Practice List

Easy (start here, 5-8 problems)

Medium (the meat of interview prep, 6-8 problems)

Hard (after you have grinded the above, 5-6 problems)

Interview Questions