The Two Pointer Technique is one of the most elegant and efficient algorithmic approaches in computer science. It's a versatile technique that comes in several patterns, and today we'll dive deep into one of its most powerful variants: the Opposite Ends Pattern.
Understanding the Two Pointer Technique
Before we dive into the specific pattern, let's clarify what the Two Pointer Technique is all about:
Two Pointer Technique is an algorithmic approach that uses two pointers to traverse a data structure (typically arrays or strings) to solve problems efficiently. The technique has several common patterns:
- Opposite Ends Pattern - Start from both ends and move inward
- Fast & Slow Pointers - Two pointers moving at different speeds
- Sliding Window - Two pointers maintaining a window of elements
- Same Direction - Both pointers moving in the same direction
Today's focus: The Opposite Ends Pattern ⭐
What is the Opposite Ends Pattern?
The Opposite Ends Pattern is a specific implementation of the Two Pointer Technique where we place two pointers at the beginning and end of a data structure, then move them toward each other based on specific conditions. This pattern is particularly effective when dealing with sorted arrays or when we need to find pairs that satisfy certain criteria.
public class TwoPointerOppositeEnds {
public static ResultType twoPointerOppositeEnds(int[] arr) {
int left = 0;
int right = arr.length - 1;
while (left < right) {
// Process current pair arr[left] and arr[right]
if (conditionMet(arr[left], arr[right])) {
// Found solution or update result
return result;
} else if (needSmallerSum(arr[left], arr[right])) {
left++;
} else {
right--;
}
}
return defaultResult;
}
}
Pattern Recognition 🔍
Use the Opposite Ends Pattern of the Two Pointer Technique when you encounter:
- Sorted arrays and need to find pairs with specific properties
- Palindrome checking problems
- Target sum problems in sorted arrays
- Container/area maximization problems
- Reversing or rearranging elements
Problem Categories & Solutions
- Target Sum Problems Problem: Find if there exist two numbers in a sorted array that sum to a target.
public class TwoSumSorted {
/**
* Two Pointer Technique - Opposite Ends Pattern
* Time: O(n), Space: O(1)
*/
public static int[] twoSum(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left < right) {
int currentSum = nums[left] + nums[right];
if (currentSum == target) {
return new int[]{left, right}; // Found the pair
} else if (currentSum < target) {
left++; // Need larger sum
} else {
right--; // Need smaller sum
}
}
return new int[]{-1, -1}; // No pair found
}
public static void main(String[] args) {
int[] nums = {2, 7, 11, 15};
int target = 9;
int[] result = twoSum(nums, target);
System.out.println("Indices: [" + result[0] + ", " + result[1] + "]");
// Output: Indices: [0, 1]
}
}
Why it works: In a sorted array, if the current sum is too small, we need to increase it by moving the left pointer right. If it's too large, we decrease it by moving the right pointer left.
- Palindrome Validation Problem: Check if a string is a palindrome using the Two Pointer Technique.
public class PalindromeValidator {
/**
* Two Pointer Technique - Opposite Ends Pattern
* Time: O(n), Space: O(1)
*/
public static boolean isPalindrome(String s) {
// Clean the string: keep only alphanumeric characters
StringBuilder cleaned = new StringBuilder();
for (char c : s.toCharArray()) {
if (Character.isLetterOrDigit(c)) {
cleaned.append(Character.toLowerCase(c));
}
}
String cleanStr = cleaned.toString();
int left = 0;
int right = cleanStr.length() - 1;
while (left < right) {
if (cleanStr.charAt(left) != cleanStr.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
public static void main(String[] args) {
System.out.println(isPalindrome("A man, a plan, a canal: Panama")); // true
System.out.println(isPalindrome("race a car")); // false
}
}
- Container With Most Water Problem: Find two lines that together with the x-axis form a container that holds the most water.
public class ContainerWithMostWater {
/**
* Two Pointer Technique - Opposite Ends Pattern
* Time: O(n), Space: O(1)
*/
public static int maxArea(int[] height) {
int maxWater = 0;
int left = 0;
int right = height.length - 1;
while (left < right) {
// Calculate current area
int width = right - left;
int currentArea = Math.min(height[left], height[right]) * width;
maxWater = Math.max(maxWater, currentArea);
// Move the pointer with smaller height
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxWater;
}
public static void main(String[] args) {
int[] heights = {1, 8, 6, 2, 5, 4, 8, 3, 7};
System.out.println("Max area: " + maxArea(heights)); // Output: 49
}
}
Key insight: We always move the pointer with the smaller height because moving the taller one cannot lead to a larger area.
- Three Sum Problem Problem: Find all unique triplets that sum to zero using Two Pointer Technique.
import java.util.*;
public class ThreeSum {
/**
* Two Pointer Technique - Opposite Ends Pattern (nested)
* Time: O(n²), Space: O(1) excluding output
*/
public static List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums); // Essential for this approach
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
// Skip duplicates for the first element
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
int target = -nums[i];
while (left < right) {
int currentSum = nums[left] + nums[right];
if (currentSum == target) {
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 (currentSum < target) {
left++;
} else {
right--;
}
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {-1, 0, 1, 2, -1, -4};
List<List<Integer>> result = threeSum(nums);
System.out.println("Triplets: " + result);
// Output: Triplets: [[-1, -1, 2], [-1, 0, 1]]
}
}
- Remove Duplicates from Sorted Array Problem: Remove duplicates in-place using Two Pointer Technique and return the new length.
public class RemoveDuplicates {
/**
* Two Pointer Technique - Same Direction Variation
* Time: O(n), Space: O(1)
*/
public static int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
// slow pointer tracks position for next unique element
int slow = 1;
for (int fast = 1; fast < nums.length; fast++) {
if (nums[fast] != nums[fast - 1]) {
nums[slow] = nums[fast];
slow++;
}
}
return slow;
}
public static void main(String[] args) {
int[] nums = {1, 1, 2, 2, 3, 4, 4, 5};
int length = removeDuplicates(nums);
System.out.println("New length: " + length); // Output: 5
System.out.print("Array: [");
for (int i = 0; i < length; i++) {
System.out.print(nums[i] + (i < length - 1 ? ", " : ""));
}
System.out.println("]"); // Output: [1, 2, 3, 4, 5]
}
}
Advanced Pattern Implementation
Trapping Rain Water
public class TrappingRainWater {
/**
* Two Pointer Technique - Opposite Ends Pattern
* Calculate trapped rainwater
* Time: O(n), Space: O(1)
*/
public static int trap(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int waterTrapped = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
waterTrapped += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
waterTrapped += rightMax - height[right];
}
right--;
}
}
return waterTrapped;
}
public static void main(String[] args) {
int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
System.out.println("Water trapped: " + trap(height)); // Output: 6
}
}
Common Pitfalls & Tips ⚠️
Pitfalls to Avoid:
Confusing Two Pointer patterns - Make sure you're using Opposite Ends when appropriate
Forgetting to handle duplicates in sum problems
Incorrect termination condition (use left < right, not left <= right)
Not considering edge cases like empty arrays
Moving both pointers simultaneously when you should move one
Pro Tips:
Master all Two Pointer patterns - Each has its use case
Always sort first for sum-related problems in Opposite Ends pattern
Use meaningful variable names (left, right vs i, j)
Document your movement logic with comments
Test with edge cases: [], [1], [1,1]
Time & Space Complexity Analysis
Here's a copyable complexity reference for the problems we covered:
| Problem Type | Time Complexity | Space Complexity | Two Pointer Pattern |
|---|---|---|---|
| Two Sum (sorted) | O(n) | O(1) | Opposite Ends |
| Palindrome Check | O(n) | O(1) | Opposite Ends |
| Container Water | O(n) | O(1) | Opposite Ends |
| Three Sum | O(n²) | O(1) | Nested Opposite Ends |
| Rain Water Trap | O(n) | O(1) | Opposite Ends |
| Remove Duplicates | O(n) | O(1) | Same Direction |
Legend:
- O(n): Linear time - single pass through array
- O(n²): Quadratic time - nested loops (Three Sum uses nested two-pointer)
- O(1): Constant space - only using a few variables
Practice Problems 💪
Ready to master the Opposite Ends Pattern of the Two Pointer Technique? Try these problems:
Beginner Level:
Valid Palindrome (LeetCode 125)
Two Sum II - Input Array Is Sorted (LeetCode 167)
Remove Duplicates from Sorted Array (LeetCode 26)
Intermediate Level:
3Sum (LeetCode 15)
Container With Most Water (LeetCode 11)
Trapping Rain Water (LeetCode 42)
Advanced Level:
4Sum (LeetCode 18)
3Sum Closest (LeetCode 16)
Valid Palindrome II (LeetCode 680)
The Opposite Ends Pattern is just one powerful variant of the Two Pointer Technique, but it's fundamental for solving a wide variety of algorithmic problems efficiently. By mastering this specific pattern, you'll be equipped to tackle sorted array problems, palindrome validations, and optimization challenges with elegant O(n) solutions.
Remember: The Two Pointer Technique has multiple patterns, and recognizing which pattern to apply is key to success. The Opposite Ends Pattern excels when you need to examine pairs from both ends of your data structure.
The key is practice and pattern recognition. Start with the basic Opposite Ends problems, understand the underlying logic, then explore other Two Pointer patterns like Fast & Slow Pointers and Sliding Window.
What's your favorite Two Pointer Technique problem? Have you used other patterns like Fast & Slow Pointers? Share in the comments below! And stay tuned for the next post in this series where we'll explore the Fast & Slow Pointers Pattern of the Two Pointer Technique. 🚀
Top comments (0)