Chapter 3
Two Pointers in Java
Java Data Structures & Algorithms Series
The Two Pointers technique uses two variables pointing to different positions in an array or string,
moving them strategically to reduce a nested O(n²) loop down to a single O(n) pass. It is one of the
most frequently tested patterns in interviews.
1 The Core Idea
Instead of checking every pair with two nested loops, place one pointer at the start and one at the
end, then move them toward each other based on a condition.
Brute Force — O(n²): Two Pointers — O(n):
for i in 0..n: left = 0, right = n-1
for j in i+1..n: while left < right:
check pair (i,j) check pair (left, right)
move left++ or right--
2 Types of Two Pointer Problems
Type Setup Example
Opposite ends left=0, right=n-1, move inward Two Sum sorted, palindrome
Same direction slow & fast pointer Remove duplicates, cycle
detection
Sliding window expand right, shrink left Longest substring (Chapter 4)
Two arrays one pointer per array Merge sorted arrays
3 Pattern 1 — Two Sum in Sorted Array
Problem: Find two numbers that add up to target in a sorted array.
arr = [1, 2, 3, 4, 6], target = 6
Answer: indices [1, 3] → 2 + 4 = 6
public static int[] twoSum(int[] arr, int target) {
int left = 0, right = [Link] - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == target)
return new int[]{left, right}; // found!
else if (sum < target)
left++; // need bigger sum → move left forward
else
right--; // need smaller sum → move right backward
}
return new int[]{-1, -1};
}
// Time: O(n) | Space: O(1)
Trace walkthrough:
arr=[1,2,3,4,6], target=6
left=0, right=4 → 1+6=7 > 6 → right--
left=0, right=3 → 1+4=5 < 6 → left++
left=1, right=3 → 2+4=6 == 6 → return [1,3] ✅
4 Pattern 2 — Valid Palindrome
Problem: Check if a string is a palindrome (ignoring non-alphanumeric characters).
"A man, a plan, a canal: Panama" → true
"race a car" → false
public static boolean isPalindrome(String s) {
int left = 0, right = [Link]() - 1;
while (left < right) {
while (left < right && ))
left++;
while (left < right && ))
right--;
if ([Link]([Link](left))
!= [Link]([Link](right)))
return false;
left++;
right--;
}
return true;
}
// Time: O(n) | Space: O(1)
5 Pattern 3 — 3Sum (Three Numbers Sum to Zero)
Problem: Find all unique triplets that sum to 0.
nums = [-4, -1, -1, 0, 1, 2]
Answer: [[-1,-1,2], [-1,0,1]]
Strategy: Sort → Fix one element → Two Pointers on the rest.
public static List<List<Integer>> threeSum(int[] nums) {
[Link](nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < [Link] - 2; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue; // skip duplicates
int left = i + 1, right = [Link] - 1;
int target = -nums[i];
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
[Link]([Link](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 < target) left++;
else right--;
}
}
return result;
}
// Time: O(n²) | Space: O(1) excluding output
6 Pattern 4 — Container with Most Water
Problem: Find two lines that form a container holding the most water.
heights = [1,8,6,2,5,4,8,3,7]
Answer: 49 (lines at index 1 and 8: min(8,7)=7, width=7 → 7×7=49)
public static int maxWater(int[] height) {
int left = 0, right = [Link] - 1;
int maxWater = 0;
while (left < right) {
int h = [Link](height[left], height[right]);
int w = right - left;
maxWater = [Link](maxWater, h * w);
// Move the shorter line inward
if (height[left] < height[right]) left++;
else right--;
}
return maxWater;
}
// Time: O(n) | Space: O(1)
⭐ Why move the shorter line? Moving the taller line can only decrease width without guaranteeing a
taller height. Moving the shorter line is the only chance of finding a larger container.
7 Pattern 5 — Remove Duplicates from Sorted Array
Problem: Remove duplicates in-place, return count of unique elements.
arr = [0,0,1,1,1,2,2,3,3,4]
After: [0,1,2,3,4,_,_,_,_,_] → return 5
Slow & Fast Pointer (Same Direction)
public static int removeDuplicates(int[] nums) {
if ([Link] == 0) return 0;
int slow = 0; // slow tracks position for next unique element
for (int fast = 1; fast < [Link]; fast++) {
if (nums[fast] != nums[slow]) {
slow++;
nums[slow] = nums[fast];
}
}
return slow + 1;
}
// Time: O(n) | Space: O(1)
Trace walkthrough:
[0,0,1,1,2]
slow=0, fast=1 → 0==0, skip
slow=0, fast=2 → 0!=1 → slow=1, arr[1]=1 → [0,1,1,1,2]
slow=1, fast=3 → 1==1, skip
slow=1, fast=4 → 1!=2 → slow=2, arr[2]=2 → [0,1,2,1,2]
return 3 ✅
8 Pattern 6 — Sort Colors (Dutch National Flag)
Problem: Sort an array containing only 0s, 1s, and 2s in one pass.
arr = [2,0,2,1,1,0]
After: [0,0,1,1,2,2]
Three Pointers — Low, Mid, High
public static void sortColors(int[] nums) {
int low = 0, mid = 0, high = [Link] - 1;
while (mid <= high) {
if (nums[mid] == 0) {
swap(nums, low, mid);
low++; mid++; // 0 goes to front
} else if (nums[mid] == 1) {
mid++; // 1 stays in middle
} else {
swap(nums, mid, high);
high--; // 2 goes to back (don't increment mid!)
}
}
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp;
}
// Time: O(n) | Space: O(1)
Trace walkthrough:
[2,0,2,1,1,0]
mid=0, nums[0]=2 → swap(0,5) → [0,0,2,1,1,2], high=4
mid=0, nums[0]=0 → swap(0,0) → low=1, mid=1
mid=1, nums[1]=0 → swap(1,1) → low=2, mid=2
mid=2, nums[2]=2 → swap(2,4) → [0,0,1,1,2,2], high=3
mid=2, nums[2]=1 → mid=3
mid=3, nums[3]=1 → mid=4 > high=3, done ✅
9 Pattern 7 — Linked List Cycle Detection (Floyd's Algorithm)
Problem: Detect if a linked list has a cycle using slow & fast pointers.
1 → 2 → 3 → 4 → 5
↑ ↓
└── 7 ← 6 ← cycle!
public static boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && [Link] != null) {
slow = [Link]; // move 1 step
fast = [Link]; // move 2 steps
if (slow == fast) return true; // they meet → cycle exists
}
return false;
}
// Time: O(n) | Space: O(1)
Find Cycle Start Node
public static ListNode detectCycleStart(ListNode head) {
ListNode slow = head, fast = head;
// Phase 1: Detect cycle
while (fast != null && [Link] != null) {
slow = [Link];
fast = [Link];
if (slow == fast) break;
}
if (fast == null || [Link] == null) return null;
// Phase 2: Find cycle start
// Move slow to head; both pointers move 1 step → meet at cycle start
slow = head;
while (slow != fast) {
slow = [Link];
fast = [Link];
}
return slow;
}
// Time: O(n) | Space: O(1)
10 Pattern 8 — Merge Two Sorted Arrays
Problem: Merge nums2 into nums1 in-place. nums1 has enough extra space.
nums1 = [1,2,3,0,0,0], m=3
nums2 = [2,5,6], n=3
Result: [1,2,2,3,5,6]
Trick — Fill from the back to avoid overwriting existing elements.
public static void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1; // pointer for nums1
int p2 = n - 1; // pointer for nums2
int p = m + n - 1; // merged position (back of nums1)
while (p1 >= 0 && p2 >= 0) {
if (nums1[p1] > nums2[p2])
nums1[p--] = nums1[p1--];
else
nums1[p--] = nums2[p2--];
}
while (p2 >= 0)
nums1[p--] = nums2[p2--]; // copy remaining nums2 elements
}
// Time: O(m+n) | Space: O(1)
11 Pattern 9 — Trapping Rain Water
The two-pointer approach solves this in O(1) space without a stack.
public static int trap(int[] height) {
int left = 0, right = [Link] - 1;
int leftMax = 0, rightMax = 0, water = 0;
while (left < right) {
if (height[left] <= height[right]) {
if (height[left] >= leftMax) leftMax = height[left];
else water += leftMax - height[left];
left++;
} else {
if (height[right] >= rightMax) rightMax = height[right];
else water += rightMax - height[right];
right--;
}
}
return water;
}
// Time: O(n) | Space: O(1)
12 Full Runnable Java Program
import [Link].*;
public class Chapter3TwoPointers {
public static void main(String[] args) {
// Two Sum sorted
int[] arr = {1, 2, 3, 4, 6};
[Link]("Two Sum: " + [Link](twoSum(arr, 6))); //
[1,3]
// Palindrome
[Link]("Palindrome: " +
isPalindrome("A man, a plan, a canal: Panama")); // true
// 3Sum
int[] nums = {-4, -1, -1, 0, 1, 2};
[Link]("3Sum: " + threeSum(nums)); // [[-1,-1,2],[-
1,0,1]]
// Container with most water
int[] heights = {1,8,6,2,5,4,8,3,7};
[Link]("Max Water: " + maxWater(heights)); // 49
// Remove Duplicates
int[] dup = {0,0,1,1,1,2,2,3,3,4};
[Link]("Remove Dups count: " + removeDuplicates(dup)); // 5
// Sort Colors
int[] colors = {2,0,2,1,1,0};
sortColors(colors);
[Link]("Sort Colors: " + [Link](colors)); //
[0,0,1,1,2,2]
// Merge sorted arrays
int[] nums1 = {1,2,3,0,0,0};
merge(nums1, 3, new int[]{2,5,6}, 3);
[Link]("Merged: " + [Link](nums1)); // [1,2,2,3,5,6]
// Trapping rain water
int[] h = {0,1,0,2,1,0,1,3,2,1,2,1};
[Link]("Rain Water: " + trap(h)); // 6
}
static int[] twoSum(int[] arr, int target) {
int l = 0, r = [Link] - 1;
while (l < r) { int s = arr[l]+arr[r]; if (s==target) return new int[]{l,r};
else if (s<target) l++; else r--; }
return new int[]{-1,-1};
}
static boolean isPalindrome(String s) {
int l = 0, r = [Link]()-1;
while (l < r) {
while (l<r && )) l++;
while (l<r && )) r--;
if ([Link]([Link](l)) !=
[Link]([Link](r))) return false;
l++; r--;
}
return true;
}
static List<List<Integer>> threeSum(int[] nums) {
[Link](nums); List<List<Integer>> res = new ArrayList<>();
for (int i = 0; i < [Link]-2; i++) {
if (i > 0 && nums[i]==nums[i-1]) continue;
int l = i+1, r = [Link]-1, t = -nums[i];
while (l < r) {
int s = nums[l]+nums[r];
if (s==t) { [Link]([Link](nums[i],nums[l],nums[r]));
while (l<r && nums[l]==nums[l+1]) l++;
while (l<r && nums[r]==nums[r-1]) r--;
l++; r--;
} else if (s<t) l++; else r--;
}
}
return res;
}
static int maxWater(int[] h) {
int l=0, r=[Link]-1, max=0;
while (l<r) { max=[Link](max,[Link](h[l],h[r])*(r-l)); if (h[l]<h[r]) l+
+; else r--; }
return max;
}
static int removeDuplicates(int[] nums) {
int slow=0;
for (int fast=1; fast<[Link]; fast++) if (nums[fast]!=nums[slow])
nums[++slow]=nums[fast];
return slow+1;
}
static void sortColors(int[] nums) {
int lo=0, mid=0, hi=[Link]-1;
while (mid<=hi) {
if (nums[mid]==0) { int t=nums[lo];nums[lo]=nums[mid];nums[mid]=t; lo+
+;mid++; }
else if (nums[mid]==1) mid++;
else { int t=nums[mid];nums[mid]=nums[hi];nums[hi]=t; hi--; }
}
}
static void merge(int[] nums1, int m, int[] nums2, int n) {
int p1=m-1, p2=n-1, p=m+n-1;
while (p1>=0 && p2>=0) nums1[p--] = nums1[p1]>nums2[p2] ? nums1[p1--] :
nums2[p2--];
while (p2>=0) nums1[p--] = nums2[p2--];
}
static int trap(int[] h) {
int l=0, r=[Link]-1, lm=0, rm=0, w=0;
while (l<r) { if (h[l]<=h[r]) { if (h[l]>=lm) lm=h[l]; else w+=lm-h[l]; l++;
} else { if (h[r]>=rm) rm=h[r]; else w+=rm-h[r]; r--; } }
return w;
}
}
13 Practice Problems for Chapter 3
Solve in this order:
Difficulty Problem
Easy Valid palindrome (LeetCode #125)
Easy Merge sorted array (LeetCode #88)
Easy Remove duplicates from sorted array (LeetCode
#26)
Medium Two sum II — sorted input (LeetCode #167)
Medium 3Sum (LeetCode #15)
Medium Container with most water (LeetCode #11)
Medium Sort colors — Dutch National Flag (LeetCode #75)
Medium 4Sum (LeetCode #18) — extend 3Sum logic
Hard Trapping rain water (LeetCode #42)
Hard Minimum window substring (LeetCode #76)
💡 Key Insight: The hardest part of Two Pointers is knowing which pointer to move and when.
The rule is always: move the pointer that gives you the best chance of improving your answer.
• Two Sum → move left if sum is too small; move right if too large
• Container with Water → always move the shorter line inward
• Dutch Flag → only advance mid when the element is already in place
This decision logic is what separates a working solution from an optimal one. Next up is Chapter 4
— Sliding Window! 🚀