Two-Pointer Question Sheet

1. Pair Sum / Two-Sum (Sorted Array)

Problem: Find two numbers in a sorted array that add up to a target sum.

Example

Input: arr = [1, 2, 3, 4, 6], target = 6
Output: [1, 3]  # Indices of the numbers 2 and 4

Algorithms:

• Brute-Force (O(n^2)) - Check all pairs.
• Two-Pointer (O(n)) - Move pointers from both ends (Best for Sorted Array).
• Hash Map (O(n)) - Store values in a dictionary for quick lookup (Best for Unsorted Array).

2. Triplet Sum / Three-Sum

Problem: Find three numbers that sum to a target.

Example

Input: arr = [-1, 0, 1, 2, -1, -4], target = 0
Output: [[-1, -1, 2], [-1, 0, 1]]

Algorithms:

• Brute-Force (O(n^3)) - Check all triplets.
• Sorting + Two-Pointer (O(n^2)) - Sort array, fix one element, use two-pointer.
• Hashing (O(n^2)) - Store elements in a hash map for quick lookup.

3. Remove Duplicates (Sorted Array)

Problem: Remove duplicates in-place.

Example

Input: arr = [1, 1, 2, 2, 3, 4, 4]
Output: [1, 2, 3, 4] (unique elements in-place)

Algorithms:

• Brute-Force (O(n) space, O(n) time) - Use a set to track unique values.
• Two-Pointer (O(1) space, O(n) time) - Modify the array in-place.

4. Container With Most Water

Problem: Find two lines that form a container with the most water.

Example

Input: height = [1, 8, 6, 2, 5, 4, 8, 3, 7]
Output: 49

Algorithms:

• Brute-Force (O(n^2)) - Check all pairs of heights.
• Two-Pointer (O(n)) - Move pointers inward to maximize area.

5. Merge Two Sorted Arrays

Problem: Merge two sorted arrays into one sorted array.

Example

Input: arr1 = [1, 3, 5], arr2 = [2, 4, 6]
Output: [1, 2, 3, 4, 5, 6]

Algorithms:

• Brute-Force (O(n log n)) - Merge and sort.
• Two-Pointer (O(n)) - Compare elements and merge in a single pass.
• In-place Merge (O(n), O(1) space) - Modify without extra space.

6. Move Zeros to End

Problem: Move all zeros to the end while maintaining the order of other elements.

Example

Input: arr = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

Algorithms:

• Brute-Force (O(n) space, O(n) time) - Use extra array.
• Two-Pointer (O(1) space, O(n) time) - Swap non-zero elements in-place.

7. Valid Palindrome

Problem: Check if a string is a palindrome (ignoring non-alphanumeric characters).

Example

Input: s = "A man, a plan, a canal: Panama"
Output: True

Algorithms:

• Brute-Force (O(n) space, O(n) time) - Reverse and compare.
• Two-Pointer (O(1) space, O(n) time) - Compare characters from both ends.

8. Sort Colors (Dutch National Flag Problem)

Problem: Sort an array containing 0s, 1s, and 2s in-place.

Example

Input: arr = [2, 0, 2, 1, 1, 0]
Output: [0, 0, 1, 1, 2, 2]

Algorithms:

• Brute-Force (O(n log n)) - Sort using built-in sorting.
• Two-Pointer / Three-Way Partitioning (O(n)) - Place 0s, 1s, and 2s in correct positions.

9. Find Intersection of Two Sorted Arrays

Problem: Find the intersection of two sorted arrays.

Example

Input: arr1 = [1, 2, 3, 4, 5], arr2 = [3, 4, 5, 6, 7]
Output: [3, 4, 5]

Algorithms:

• Brute-Force (O(n*m)) - Check each element.
• Two-Pointer (O(n + m)) - Traverse both arrays simultaneously.

10. Longest Substring Without Repeating Characters

Problem: Find the length of the longest substring without repeating characters.

Example

Input: s = "abcabcbb"
Output: 3  # "abc" is the longest substring

Algorithms:

• Brute-Force (O(n^2)) - Generate all substrings.
• Sliding Window + Two-Pointer (O(n)) - Expand and contract window dynamically.

Key Takeaways for Interviews

Use Two-Pointer when:

• The array is sorted.
• You need to compare elements from both ends.
• In-place modifications are required.

Sorting before using Two-Pointer is key for:

• Three-Sum
• Pair problems in unsorted arrays

Hash Map is better for:

• Finding sums in unsorted arrays (Two-Sum).