Two Pointers
Java solutions with explanations, time and space complexity for Two Pointers problems from Blind 75.
Two Pointers
This section covers problems that can be efficiently solved using the two-pointer technique. This pattern is particularly useful for array and string problems where you need to compare or manipulate elements from different positions.
1. Valid Palindrome (Easy)
Problem: A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
Example:
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.Solution:
class Solution {
public boolean isPalindrome(String s) {
int left = 0, 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;
}
}Time Complexity: O(n) Space Complexity: O(1)
2. 3Sum (Medium)
Problem: Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]Solution:
class Solution {
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++) {
// Skip duplicates
if (i > 0 && nums[i] == nums[i-1]) continue;
int left = i + 1, 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]));
// Skip duplicates
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;
}
}Time Complexity: O(n²) Space Complexity: O(1) - excluding the output array
3. Container With Most Water (Medium)
Problem: You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Example:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The maximum area is obtained by choosing height[1] = 8 and height[8] = 7.Solution:
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length - 1;
int maxArea = 0;
while (left < right) {
int width = right - left;
int h = Math.min(height[left], height[right]);
maxArea = Math.max(maxArea, width * h);
if (height[left] < height[right]) {
left++;
} else {
right--;
}
}
return maxArea;
}
}Time Complexity: O(n) Space Complexity: O(1)
Key Insight: The area is limited by the shorter of the two heights. By moving the pointer with the shorter height inward, we might find a larger area.
4. Trapping Rain Water (Hard)
Problem: Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.
Example:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water are being trapped.Solution:
class Solution {
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int 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 Complexity: O(n) Space Complexity: O(1)
Alternative Approach (Pre-computation):
class Solution {
public int trap(int[] height) {
int n = height.length;
int[] leftMax = new int[n];
int[] rightMax = new int[n];
// Calculate left max heights
leftMax[0] = height[0];
for (int i = 1; i < n; i++) {
leftMax[i] = Math.max(leftMax[i-1], height[i]);
}
// Calculate right max heights
rightMax[n-1] = height[n-1];
for (int i = n-2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i+1], height[i]);
}
// Calculate trapped water
int water = 0;
for (int i = 0; i < n; i++) {
water += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return water;
}
}Time Complexity: O(n) Space Complexity: O(n)
5. Remove Duplicates from Sorted Array (Easy)
Problem: Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Example:
Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.Solution:
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) return 0;
int k = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[i-1]) {
nums[k] = nums[i];
k++;
}
}
return k;
}
}Time Complexity: O(n) Space Complexity: O(1)
6. Remove Element (Easy)
Problem: Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.
Return k after placing the final result in the first k slots of nums.
Example:
Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.Solution:
class Solution {
public int removeElement(int[] nums, int val) {
int k = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != val) {
nums[k] = nums[i];
k++;
}
}
return k;
}
}Time Complexity: O(n) Space Complexity: O(1)
7. Move Zeroes (Easy)
Problem: Given an integer array nums, move all 0’s to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
Example:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]Solution:
class Solution {
public void moveZeroes(int[] nums) {
int nonZeroIndex = 0;
// Move all non-zero elements to the front
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[nonZeroIndex] = nums[i];
nonZeroIndex++;
}
}
// Fill the rest with zeros
for (int i = nonZeroIndex; i < nums.length; i++) {
nums[i] = 0;
}
}
}Time Complexity: O(n) Space Complexity: O(1)
8. Two Sum II - Input Array Is Sorted (Medium)
Problem: Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.
Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2.
The tests are generated such that there is exactly one solution. You may not use the same element twice.
Example:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].Solution:
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0, right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left + 1, right + 1};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return new int[]{};
}
}Time Complexity: O(n) Space Complexity: O(1)
Key Takeaways
- Two-Pointer Technique: Use two pointers to traverse arrays from different ends or positions
- Sorting First: Many two-pointer problems benefit from sorting the array first
- Skip Duplicates: When dealing with sorted arrays, skip duplicates to avoid redundant work
- Greedy Approach: Often the optimal solution involves making locally optimal choices
- In-Place Operations: Two-pointer technique is excellent for in-place array modifications
- Boundary Conditions: Always consider edge cases like empty arrays or single elements