Top Java Two Pointer Interview Questions and Answers
Master Java Two Pointer interviews with frequently asked questions covering opposite-direction pointers, slow-fast pointers, in-place writes, Three Sum, Trapping Rain Water, Container With Most Water, duplicate removal, complexity analysis, and senior-level discussions.
Introduction
The Two Pointer pattern is one of the most important techniques in coding interviews.
It appears in problems involving:
- Sorted array pair searching
- In-place array modification
- Duplicate removal
- Partitioning
- Container area maximization
- Water trapping
- Triplet finding
- Palindrome checking
- String compression
Companies frequently use Two Pointer questions to evaluate whether candidates can:
- Move from O(n²) brute force to O(n) optimal solutions
- Reason about pointer movement correctness
- Handle edge cases involving duplicates and equal values
- Write clean, production-quality in-place Java code
- Explain invariants and correctness proofs
- Discuss trade-offs between approaches
This article consolidates the most important Two Pointer interview concepts, coding patterns, and frequently asked questions with full Java implementations.
1. What Is the Two Pointer Technique?
Answer
The Two Pointer technique uses two index variables that traverse a data structure — typically an array or string — to solve a problem more efficiently than a nested loop approach.
Instead of comparing every pair with two nested loops in O(n²), two pointers narrow the search space at each step.
The two main forms are:
Opposite-Direction Pointers:
L R
↓ ↓
[ , , , , , , ]
L moves right, R moves left
Used when the array is sorted and pairs need to be found.
Same-Direction Slow-Fast Pointers:
graph TD
S["S"] --> F["F"]
F["F"] --> N_["( , , , , , , )"]
N_["( , , , , , , )"] --> Both_move_left_to_right_at_d["Both move left to right at different speeds"]
Used for in-place writes, duplicate removal, and partition problems.
2. When Should You Use Two Pointers?
Answer
Two Pointers are useful when:
- The array or string is sorted (enables opposite-direction approach).
- You need to find a pair or triplet satisfying a condition.
- You need to modify an array in-place with O(1) extra space.
- You have a read pointer and a write pointer (slow-fast pattern).
- A nested loop can be reduced to a linear scan.
Two Pointers are not the best choice when:
- The array is unsorted and sorting is expensive.
- You need original indexes after sorting (use HashMap).
- The problem requires non-adjacent comparisons without a clear ordering rule.
3. What Are the Two Pointer Patterns?
Answer
| Pattern | Pointer Movement | Common Use |
|---|---|---|
| Opposite Direction | Left → and ← Right | Sorted pair sum, palindrome check, container area |
| Slow-Fast (Same Direction) | Both left to right, different speeds | Remove duplicates, remove element, move zeroes |
| Anchor + Scanner | One fixed, one scanning | Three Sum outer loop + inner two pointer |
| Read-Write | Read scans, write position tracks | In-place compaction |
4. What Is the Time and Space Complexity of Two Pointer Solutions?
Answer
| Complexity | Value |
|---|---|
| Time | O(n) |
| Space | O(1) |
Each pointer moves at most n steps in one direction.
No extra data structures are needed.
Compare with:
| Approach | Time | Space |
|---|---|---|
| Brute Force | O(n²) | O(1) |
| HashMap | O(n) | O(n) |
| Two Pointer | O(n) | O(1) |
Two Pointer achieves the same linear time as HashMap but with constant space.
5. How Do You Solve Two Sum II (Sorted Array)?
Answer
Given a sorted array, find two elements that sum to a target.
Use opposite-direction pointers.
If the current sum is too small, move the left pointer right. If the current sum is too large, move the right pointer left.
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
long sum =
(long) numbers[left]
+ numbers[right];
if (sum == target) {
return new int[]{left + 1, right + 1};
}
if (sum < target) {
left++;
} else {
right--;
}
}
throw new IllegalArgumentException(
"No valid pair exists");
}
Complexity:
Time: O(n)
Space: O(1)
6. Why Can You Move the Left Pointer When the Sum Is Too Small?
Answer
Because the array is sorted:
All values to the left of right are ≤ numbers[right].
If the current sum is too small:
numbers[left] + numbers[right] < target
Then pairing numbers[left] with any value to the left of right produces an even smaller sum.
numbers[left] cannot participate in any valid pair.
Moving left++ safely discards it.
7. Why Can You Move the Right Pointer When the Sum Is Too Large?
Answer
Because the array is sorted:
All values to the right of left are ≥ numbers[left].
If the current sum is too large:
numbers[left] + numbers[right] > target
Then pairing numbers[right] with any value to the right of left produces an even larger sum.
numbers[right] cannot participate in any valid pair.
Moving right-- safely discards it.
8. How Do You Solve the Three Sum Problem?
Answer
Given an unsorted array, find all unique triplets that sum to zero.
Sort the array first.
Fix one element with an outer loop.
Apply Two Pointer to the remaining sub-array.
Skip duplicates at every level to avoid repeated triplets.
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(
nums[i], nums[left], nums[right]));
while (left < right
&& nums[left] == nums[left + 1]) left++;
while (left < right
&& nums[right] == nums[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
Complexity:
Time: O(n²) — outer loop O(n), inner Two Pointer O(n)
Space: O(1) — excluding output list
9. Why Must You Sort Before Applying Three Sum?
Answer
Sorting is essential for two reasons:
Deduplication without a Set:
After sorting, duplicate values are adjacent.
Skipping nums[i] == nums[i-1] in the outer loop and skipping duplicate pointer values after a match prevents duplicate triplets without a HashSet.
Directional pointer movement:
The Two Pointer approach requires that:
Moving left right → increases sum
Moving right left → decreases sum
This is only valid on a sorted sub-array.
Without sorting, pointer movement would have no guaranteed effect on the sum.
10. How Do You Solve Container With Most Water?
Answer
Given an array of heights, find two lines that form a container holding the most water.
area = min(height[left], height[right]) × (right - left)
Use opposite-direction pointers.
Always move the pointer at the shorter line — moving the taller line can only decrease or maintain the area.
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int maxArea = 0;
while (left < right) {
int area =
Math.min(height[left], height[right])
* (right - left);
maxArea = Math.max(maxArea, area);
if (height[left] <= height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
Complexity:
Time: O(n)
Space: O(1)
11. Why Do You Move the Shorter Line in Container With Most Water?
Answer
The area is always limited by the shorter line:
area = min(height[left], height[right]) × width
If height[left] < height[right]:
Moving the right pointer left:
Width decreases by 1
Height is still capped by height[left] (unchanged)
New area ≤ current area — guaranteed worse
Moving the left pointer right:
Width decreases by 1
Height may increase if the next left bar is taller
New area may be larger — only hope of improvement
Therefore, always move the pointer at the shorter line.
12. How Does Container With Most Water Differ from Trapping Rain Water?
Answer
| Aspect | Container With Most Water | Trapping Rain Water |
|---|---|---|
| Formula | min(h[L], h[R]) × width |
sum(min(leftMax, rightMax) - h[i]) |
| Goal | Maximize one container's area | Sum water above all bars |
| Pointer logic | Move shorter pointer | Move pointer at smaller max |
| Output | Single maximum value | Total accumulated water |
| LeetCode | #11 | #42 |
Container With Most Water uses the current heights of the two endpoint bars.
Trapping Rain Water uses the running maximum heights seen from each direction.
13. How Do You Solve Trapping Rain Water?
Answer
Water above each bar equals:
max(0, min(leftMax, rightMax) - height[i])
Use Two Pointers with running leftMax and rightMax.
When height[left] <= height[right], process the left side — the right side is already proven to be at least as tall as leftMax.
public int trap(int[] height) {
int left = 0;
int right = height.length - 1;
int leftMax = 0;
int rightMax = 0;
int total = 0;
while (left < right) {
if (height[left] <= height[right]) {
leftMax = Math.max(leftMax, height[left]);
total += leftMax - height[left];
left++;
} else {
rightMax = Math.max(rightMax, height[right]);
total += rightMax - height[right];
right--;
}
}
return total;
}
Complexity:
Time: O(n)
Space: O(1)
14. Why Does the Two Pointer Approach for Trapping Rain Water Not Require Both Max Arrays?
Answer
The prefix/suffix approach precomputes both leftMax[] and rightMax[] because each bar needs both values simultaneously.
The Two Pointer approach avoids this using one key observation:
When height[left] <= height[right]:
height[right] >= height[left]
rightMax >= height[right] >= height[left] >= leftMax
Therefore: min(leftMax, rightMax) = leftMax
The water above left is exactly leftMax - height[left].
The exact value of rightMax does not matter — it is already guaranteed to be larger than leftMax.
This lazy evaluation eliminates the need for the suffix array.
15. How Do You Remove Duplicates from a Sorted Array In-Place?
Answer
Use a slow-fast pointer pattern.
slow is the write position.
fast scans the array.
When nums[fast] != nums[slow], advance slow and write the new unique value.
public int removeDuplicates(int[] nums) {
int slow = 0;
for (int fast = 1;
fast < nums.length;
fast++) {
if (nums[fast] != nums[slow]) {
nums[++slow] = nums[fast];
}
}
return slow + 1;
}
Complexity:
Time: O(n)
Space: O(1)
Return slow + 1, not slow — slow is a zero-based index.
16. What Is the Invariant for the Remove Duplicates Algorithm?
Answer
At every iteration:
nums[0..slow] contains exactly the unique elements
seen so far, in their original sorted order.
Base case: Before the loop, slow = 0. nums[0..0] holds the first element — trivially unique.
Inductive step:
- If
nums[fast] == nums[slow]: duplicate —slowdoes not advance. Prefix unchanged. - If
nums[fast] != nums[slow]: new unique value — write it atslow + 1. Prefix extended by one.
Termination: fast advances every iteration. Loop ends at fast == nums.length.
At termination, nums[0..slow] is the complete unique prefix. Return slow + 1.
17. How Do You Remove All Occurrences of a Given Value In-Place?
Answer
Use a write pointer slow.
Copy every element that is not equal to val into nums[slow].
public int removeElement(int[] nums, int val) {
int slow = 0;
for (int fast = 0;
fast < nums.length;
fast++) {
if (nums[fast] != val) {
nums[slow++] = nums[fast];
}
}
return slow;
}
Complexity:
Time: O(n)
Space: O(1)
Unlike Remove Duplicates, fast starts at 0 (not 1) because there is no seed element to preserve.
Return slow directly — it already equals the count of surviving elements.
18. How Do You Move All Zeroes to the End In-Place?
Answer
Use a write pointer slow.
Copy all non-zero elements forward using swap to preserve order.
public void moveZeroes(int[] nums) {
int slow = 0;
for (int fast = 0;
fast < nums.length;
fast++) {
if (nums[fast] != 0) {
int temp = nums[slow];
nums[slow] = nums[fast];
nums[fast] = temp;
slow++;
}
}
}
Complexity:
Time: O(n)
Space: O(1)
Swapping instead of overwriting ensures zeroes are moved to the tail without losing any non-zero value.
19. How Do You Check If a String Is a Palindrome Using Two Pointers?
Answer
Use opposite-direction pointers.
Compare characters at left and right.
If they differ, not a palindrome.
Advance both pointers inward.
public boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
Complexity:
Time: O(n)
Space: O(1)
For LeetCode #125 (valid palindrome ignoring non-alphanumeric characters):
public boolean isPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
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;
}
20. How Do You Reverse an Array In-Place?
Answer
Use opposite-direction pointers.
Swap nums[left] and nums[right], then advance both.
public void reverse(int[] nums) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
Complexity:
Time: O(n)
Space: O(1)
21. How Do You Find If There Exists a Pair with a Given Difference?
Answer
Given a sorted array, find if any pair (a, b) satisfies b - a == k.
Use opposite-direction pointers.
If the current difference is less than k, advance left.
If the current difference is greater than k, advance right.
If the current difference equals k, a valid pair is found.
public boolean hasPairWithDifference(
int[] nums,
int k) {
int left = 0;
int right = 1;
while (right < nums.length) {
int diff = nums[right] - nums[left];
if (diff == k) {
return true;
}
if (diff < k) {
right++;
} else {
left++;
if (left == right) right++;
}
}
return false;
}
Complexity:
Time: O(n)
Space: O(1)
22. How Do You Find the Closest Pair Sum to a Target in a Sorted Array?
Answer
Use opposite-direction pointers.
At each step, compare the absolute difference between the current sum and the target with the best seen so far.
Move the pointer that pushes the sum closer to the target.
public int[] closestPair(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int bestDiff = Integer.MAX_VALUE;
int bestLeft = 0;
int bestRight = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
int diff = Math.abs(sum - target);
if (diff < bestDiff) {
bestDiff = diff;
bestLeft = left;
bestRight = right;
}
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
break;
}
}
return new int[]{nums[bestLeft], nums[bestRight]};
}
Complexity:
Time: O(n)
Space: O(1)
23. How Do You Partition an Array Around a Pivot (Dutch National Flag)?
Answer
Use three pointers: low, mid, and high.
Elements less than the pivot go to [0, low).
Elements equal to the pivot stay at [low, mid).
Elements greater than the pivot go to (high, n-1].
public void sortColors(int[] nums) {
int low = 0;
int mid = 0;
int 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 {
int temp = nums[mid];
nums[mid] = nums[high];
nums[high] = temp;
high--;
}
}
}
Complexity:
Time: O(n)
Space: O(1)
This is LeetCode #75 — Sort Colors. It sorts [0, 1, 2] in one pass without sorting.
24. How Do You Count Pairs with Sum Less Than a Target?
Answer
Use opposite-direction pointers on a sorted array.
When the current sum is less than the target:
All pairs (left, right), (left, right-1), ..., (left, left+1)
are all valid — there are (right - left) such pairs.
Add right - left to the count and advance left.
public int countPairsWithSumLessThan(
int[] nums,
int target) {
Arrays.sort(nums);
int left = 0;
int right = nums.length - 1;
int count = 0;
while (left < right) {
if (nums[left] + nums[right] < target) {
count += right - left;
left++;
} else {
right--;
}
}
return count;
}
Complexity:
Time: O(n log n) — dominated by sort
Space: O(1)
25. How Do You Find All Unique Pairs with a Given Sum in a Sorted Array?
Answer
Use opposite-direction pointers.
When a pair is found, record it, then skip all duplicates for both pointers before continuing.
public List<int[]> allPairsWithSum(
int[] nums,
int target) {
List<int[]> result = new ArrayList<>();
int left = 0;
int right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
result.add(new int[]{nums[left], nums[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;
}
Complexity:
Time: O(n)
Space: O(1) (excluding output)
26. What Is the Difference Between the Slow-Fast Pattern and the Opposite-Direction Pattern?
Answer
| Aspect | Opposite Direction | Slow-Fast (Same Direction) |
|---|---|---|
| Pointer start | Opposite ends | Same end (both at 0 or both at start) |
| Movement direction | Toward each other | Both left to right |
| Primary use | Pair finding in sorted arrays | In-place write and partition |
| Array requirement | Sorted (usually) | Not required |
| Examples | Two Sum II, Three Sum, Container, Palindrome | Remove Duplicates, Remove Element, Move Zeroes |
27. How Do You Handle Duplicates in Two Pointer Solutions?
Answer
Duplicates must be explicitly skipped to avoid:
- Counting the same pair or triplet multiple times.
- Returning duplicate results.
For the outer fixed element (Three Sum):
if (i > 0 && nums[i] == nums[i - 1]) continue;
Skip starting from i = 1 — do not skip i = 0.
For the left pointer after a match:
while (left < right && nums[left] == nums[left + 1]) left++;
For the right pointer after a match:
while (left < right && nums[right] == nums[right - 1]) right--;
After skipping duplicates, advance both pointers by one more step.
28. What Is the Loop Invariant for the Opposite-Direction Two Pointer?
Answer
For pair-sum problems on sorted arrays:
At every iteration, if a valid pair exists,
it lies within the current interval [left, right].
Each pointer movement removes an element that cannot be part of the valid pair.
When left == right:
All elements have been considered or safely discarded.
This invariant guarantees no valid pair is missed.
29. What Is Integer Overflow Risk in Two Pointer Problems?
Answer
When adding two large integers:
int sum = numbers[left] + numbers[right];
If both values are close to Integer.MAX_VALUE (~2.1 × 10^9):
2,000,000,000 + 2,000,000,000 = 4,000,000,000
This overflows int.
Safe approach using long:
long sum =
(long) numbers[left]
+ numbers[right];
The cast to long must happen before the addition.
This is relevant for Two Sum II and Container With Most Water when heights or values are large.
30. Why Is the Two Pointer Complexity O(n) and Not O(n²)?
Answer
A common misconception is that using two pointers inside a while loop means nested iterations.
In reality:
Each pointer moves monotonically in one direction.
The left pointer only moves right.
The right pointer only moves left.
Total pointer movements ≤ n - 1 from each side.
Total iterations ≤ 2(n - 1) = O(n).
There is no nested scan — both pointers share the same outer loop budget.
For Three Sum, the outer loop is O(n) and the inner Two Pointer is O(n), giving O(n²) total — still a significant improvement over the O(n³) brute force.
31. How Do You Remove Duplicates Allowing Each Element at Most Twice (LeetCode #80)?
Answer
Generalize the slow-fast pattern by comparing nums[fast] with nums[slow - 1] (two positions back instead of one).
public int removeDuplicates(int[] nums) {
if (nums.length <= 2) return nums.length;
int slow = 1;
for (int fast = 2;
fast < nums.length;
fast++) {
if (nums[fast] != nums[slow - 1]) {
nums[++slow] = nums[fast];
}
}
return slow + 1;
}
Complexity:
Time: O(n)
Space: O(1)
For the general case of allowing at most k duplicates, compare nums[fast] with nums[slow - (k - 1)].
32. How Do You Solve the Four Sum Problem?
Answer
Fix two elements with two outer loops, then apply Two Pointer to the remaining pair.
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
int n = nums.length;
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1;
int right = n - 1;
while (left < right) {
long sum =
(long) nums[i] + nums[j]
+ nums[left] + nums[right];
if (sum == target) {
result.add(Arrays.asList(
nums[i], nums[j], nums[left], nums[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;
}
Complexity:
Time: O(n³)
Space: O(1) (excluding output)
33. What Is the Difference Between Two Sum I and Two Sum II?
Answer
| Aspect | Two Sum I (LeetCode #1) | Two Sum II (LeetCode #167) |
|---|---|---|
| Array sorted? | No | Yes |
| Extra space allowed? | Yes (O(n)) | No (O(1)) |
| Optimal approach | HashMap | Two Pointer |
| Index convention | Zero-based | One-based |
| Complexity | O(n) time, O(n) space | O(n) time, O(1) space |
Use Two Pointer for Two Sum only when the array is already sorted.
Sorting an unsorted array to apply Two Pointer costs O(n log n) and loses original indexes — the HashMap approach is preferred for unsorted input.
34. How Do You Apply Two Pointer to Strings?
Answer
Two Pointer applies to strings the same way as arrays.
Common string problems:
Reverse a String:
public void reverseString(char[] s) {
int left = 0;
int right = s.length - 1;
while (left < right) {
char temp = s[left];
s[left] = s[right];
s[right] = temp;
left++;
right--;
}
}
Check Palindrome (ignoring non-alphanumeric):
Skip non-alphanumeric characters with inner while loops before comparing.
String Compression:
Use a write pointer to compact repeated characters with their count.
public int compress(char[] chars) {
int write = 0;
int i = 0;
while (i < chars.length) {
char current = chars[i];
int count = 0;
while (i < chars.length
&& chars[i] == current) {
i++;
count++;
}
chars[write++] = current;
if (count > 1) {
for (char c : Integer.toString(count).toCharArray()) {
chars[write++] = c;
}
}
}
return write;
}
35. What Are the Most Common Two Pointer Interview Mistakes?
Answer
Mistake 1 — Using left ≤ right instead of left < right:
When left == right, both pointers reference the same element.
For pair problems, this creates an invalid self-pair.
Use left < right.
Mistake 2 — Moving the Wrong Pointer:
Moving the taller pointer in Container With Most Water, or moving the right pointer when the sum is too small in Two Sum II, always produces a worse result.
Always identify which pointer should move based on the invariant.
Mistake 3 — Forgetting to Skip Duplicates After a Match:
In Three Sum and Four Sum, not skipping duplicates after recording a valid triplet/quadruplet leads to repeated results.
Mistake 4 — Returning slow Instead of slow + 1:
In Remove Duplicates, slow is a zero-based index. The count is slow + 1.
Mistake 5 — Integer Overflow:
Always use long when adding two potentially large integers.
Cast before adding, not after.
Mistake 6 — Starting fast at 0 Instead of 1 in Remove Duplicates:
slow = 0 seeds the prefix with nums[0].
fast must start at 1 to avoid comparing an element with itself.
Mistake 7 — Writing Before Advancing slow:
❌ nums[slow] = nums[fast]; // overwrites last unique value
slow++;
Correct order:
slow++;
nums[slow] = nums[fast];
Mistake 8 — Claiming O(n²) Due to Two Pointers:
Pointer count does not determine complexity.
Analyze total pointer movements — each pointer moves at most n times in one direction.
36. How Do You Decide Whether to Use Two Pointer or Sliding Window?
Answer
| Criteria | Two Pointer | Sliding Window |
|---|---|---|
| Array sorted? | Often yes | Not required |
| Finding pairs/triplets? | Yes | No |
| Sub-array sum or length? | No | Yes |
| Window shrinks and grows? | No — pointers converge | Yes |
| Example problems | Two Sum II, Three Sum, Container | Max Sum Subarray, Longest Substring |
Two Pointer is for finding elements at specific positions.
Sliding Window is for analyzing contiguous sub-arrays or substrings.
37. What Is the Senior-Level Follow-Up for Two Pointer Problems?
Answer
Senior engineers are expected to explain:
Correctness:
Why does pointer movement never skip the valid answer?
State the loop invariant explicitly.
Complexity:
Prove that total iterations are O(n), not O(n²).
Space:
Explain why no extra data structure is needed.
Compare with HashMap and prefix-array alternatives.
Generalizations:
How does the problem scale to Three Sum, Four Sum, or k-Sum?
How does it extend to 2D matrices or 3D problems (Trapping Rain Water II)?
Production Concerns:
Integer overflow for large values.
Null and empty array guards.
Handling streaming or file-based inputs.
38. How Do You Solve the Minimum Size Subarray Sum Using Two Pointer?
Answer
Find the minimum-length contiguous subarray with sum ≥ target.
Use a growing right pointer and a shrinking left pointer.
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int sum = 0;
int minLen = Integer.MAX_VALUE;
for (int right = 0;
right < nums.length;
right++) {
sum += nums[right];
while (sum >= target) {
minLen = Math.min(minLen, right - left + 1);
sum -= nums[left++];
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
Complexity:
Time: O(n) — each element is added and removed at most once
Space: O(1)
39. How Do You Apply Two Pointer to a Linked List?
Answer
The slow-fast pointer pattern applies directly to linked lists.
Detect a Cycle:
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null
&& fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
Find the Middle Node:
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null
&& fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
In both cases, fast moves at twice the speed of slow.
When fast reaches the end, slow is at the midpoint.
40. What Are the Top Two Pointer Problems Every Java Engineer Should Know?
Answer
| # | Problem | Pattern | LeetCode |
|---|---|---|---|
| 1 | Two Sum II — Input Array Is Sorted | Opposite direction, sorted pair | #167 |
| 2 | Three Sum | Sort + Fix + Two Pointer | #15 |
| 3 | Container With Most Water | Opposite direction, greedy | #11 |
| 4 | Trapping Rain Water | Opposite direction, running max | #42 |
| 5 | Remove Duplicates from Sorted Array | Slow-fast write | #26 |
| 6 | Remove Element | Slow-fast write | #27 |
| 7 | Move Zeroes | Slow-fast swap | #283 |
| 8 | Valid Palindrome | Opposite direction, string | #125 |
| 9 | Sort Colors (Dutch National Flag) | Three pointer partition | #75 |
| 10 | Remove Duplicates II (at most twice) | Slow-fast, k-back comparison | #80 |
| 11 | Four Sum | Sort + two outer loops + Two Pointer | #18 |
| 12 | Minimum Size Subarray Sum | Shrinkable sliding window | #209 |
These twelve problems cover every Two Pointer variant. Mastering them provides a complete foundation for Two Pointer questions at all levels.
Summary
The Two Pointer pattern is one of the most impactful optimization techniques in coding interviews.
It reduces quadratic solutions to linear time by eliminating impossible cases with directional pointer movement.
The opposite-direction pattern works on sorted arrays to find pairs and triplets.
The slow-fast pattern enables in-place array modification with O(1) extra space.
The key to correctness is always the invariant — at every step, pointer movement only discards elements that cannot contribute to the answer.
Mastering the invariant, the complexity justification, and the duplicate-skipping logic is what separates a good answer from an excellent one at senior and staff engineer interviews.
Key Takeaways
- Two Pointer reduces O(n²) brute force to O(n) by eliminating impossible pairs at each step.
- Opposite-direction pointers require a sorted array to guarantee directional validity.
- Slow-fast pointers enable in-place writes without extra memory.
- The loop invariant proves correctness — always identify it before writing code.
- Total pointer movements are O(n) — never O(n²) — because each pointer moves monotonically.
- Always use
longwhen adding two potentially large integers to avoid overflow. - Skip duplicates at every level in Three Sum and Four Sum to avoid repeated results.
- Use
left < rightto prevent a self-pair at the same index. - The Two Pointer approach for Trapping Rain Water avoids both suffix arrays by using the min-side invariant.
- The Two Pointer approach for Container With Most Water moves the shorter pointer because it is always the bottleneck.