Two Pointers Technique

What is the Two Pointers Technique?

The two pointers technique uses two index variables that move through a data structure � usually an array or string � to solve problems in O(n) time instead of O(n�). The pointers can start at opposite ends and move toward each other, or both start at the beginning and move at different speeds.

When to Use Two Pointers

Sorted arrays � finding pairs with a target sum
Palindrome checks � comparing characters from both ends
Removing duplicates � in-place with a slow and fast pointer
Merging sorted arrays � one pointer per array
Container with most water � maximize area between two lines
Three sum / k-sum � fix one element, use two pointers for the rest

Two Sum (Sorted) and Valid Palindrome

#include <iostream>
#include <vector>
#include <string>
#include <cctype>
using namespace std;

// Two Sum II � sorted array, O(n) time, O(1) space
vector<int> twoSum(vector<int>& arr, int target) {
    int lo = 0, hi = arr.size() - 1;
    while (lo < hi) {
        int sum = arr[lo] + arr[hi];
        if (sum == target) return {lo + 1, hi + 1};  // 1-indexed
        else if (sum < target) lo++;
        else hi--;
    }
    return {};
}

// Valid Palindrome � O(n) time, O(1) space
bool isPalindrome(const string& s) {
    int lo = 0, hi = s.size() - 1;
    while (lo < hi) {
        while (lo < hi && !isalnum(s[lo])) lo++;
        while (lo < hi && !isalnum(s[hi])) hi--;
        if (tolower(s[lo]) != tolower(s[hi])) return false;
        lo++; hi--;
    }
    return true;
}

int main() {
    vector<int> arr = {2, 7, 11, 15};
    auto res = twoSum(arr, 9);
    cout << res[0] << " " << res[1] << endl;  // 1 2

    cout << boolalpha;
    cout << isPalindrome("A man, a plan, a canal: Panama") << endl;  // true
    cout << isPalindrome("race a car") << endl;                       // false
    return 0;
}

public class TwoPointers {

    // Two Sum II � sorted array
    static int[] twoSum(int[] arr, int target) {
        int lo = 0, hi = arr.length - 1;
        while (lo < hi) {
            int sum = arr[lo] + arr[hi];
            if (sum == target) return new int[]{lo + 1, hi + 1};
            else if (sum < target) lo++;
            else hi--;
        }
        return new int[]{};
    }

    // Valid Palindrome
    static boolean isPalindrome(String s) {
        int lo = 0, hi = s.length() - 1;
        while (lo < hi) {
            while (lo < hi && !Character.isLetterOrDigit(s.charAt(lo))) lo++;
            while (lo < hi && !Character.isLetterOrDigit(s.charAt(hi))) hi--;
            if (Character.toLowerCase(s.charAt(lo)) != Character.toLowerCase(s.charAt(hi)))
                return false;
            lo++; hi--;
        }
        return true;
    }

    public static void main(String[] args) {
        int[] arr = {2, 7, 11, 15};
        int[] res = twoSum(arr, 9);
        System.out.println(res[0] + " " + res[1]);  // 1 2

        System.out.println(isPalindrome("A man, a plan, a canal: Panama"));  // true
        System.out.println(isPalindrome("race a car"));                       // false
    }
}

# Two Sum II � sorted array, O(n) time, O(1) space
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:   return [lo + 1, hi + 1]  # 1-indexed
        elif s < target:  lo += 1
        else:             hi -= 1
    return []

# Valid Palindrome � ignore non-alphanumeric, case-insensitive
def is_palindrome(s):
    lo, hi = 0, len(s) - 1
    while lo < hi:
        while lo < hi and not s[lo].isalnum(): lo += 1
        while lo < hi and not s[hi].isalnum(): hi -= 1
        if s[lo].lower() != s[hi].lower(): return False
        lo += 1; hi -= 1
    return True

print(two_sum_sorted([2, 7, 11, 15], 9))                    # [1, 2]
print(is_palindrome("A man, a plan, a canal: Panama"))       # True
print(is_palindrome("race a car"))                           # False

// Two Sum II � sorted array
function twoSum(arr, target) {
    let lo = 0, hi = arr.length - 1;
    while (lo < hi) {
        const sum = arr[lo] + arr[hi];
        if (sum === target) return [lo + 1, hi + 1];
        else if (sum < target) lo++;
        else hi--;
    }
    return [];
}

// Valid Palindrome
function isPalindrome(s) {
    let lo = 0, hi = s.length - 1;
    const isAlnum = c => /[a-zA-Z0-9]/.test(c);
    while (lo < hi) {
        while (lo < hi && !isAlnum(s[lo])) lo++;
        while (lo < hi && !isAlnum(s[hi])) hi--;
        if (s[lo].toLowerCase() !== s[hi].toLowerCase()) return false;
        lo++; hi--;
    }
    return true;
}

console.log(twoSum([2, 7, 11, 15], 9));                     // [1, 2]
console.log(isPalindrome("A man, a plan, a canal: Panama")); // true
console.log(isPalindrome("race a car"));                     // false

Remove Duplicates and Container With Most Water

Remove Duplicates In-Place and Container With Most Water

#include <iostream>
#include <vector>
using namespace std;

// Remove duplicates from sorted array in-place � O(n)
// slow pointer writes unique values; fast pointer scans ahead
int removeDuplicates(vector<int>& arr) {
    if (arr.empty()) return 0;
    int slow = 0;
    for (int fast = 1; fast < arr.size(); fast++) {
        if (arr[fast] != arr[slow]) {
            slow++;
            arr[slow] = arr[fast];
        }
    }
    return slow + 1;  // new length
}

// Container With Most Water � O(n)
// Move the pointer with the shorter height inward
int maxWater(vector<int>& height) {
    int lo = 0, hi = height.size() - 1, maxArea = 0;
    while (lo < hi) {
        int area = min(height[lo], height[hi]) * (hi - lo);
        maxArea = max(maxArea, area);
        if (height[lo] < height[hi]) lo++;
        else hi--;
    }
    return maxArea;
}

int main() {
    vector<int> arr = {1, 1, 2, 2, 3, 4, 4};
    int len = removeDuplicates(arr);
    cout << "Unique count: " << len << endl;  // 4

    vector<int> h = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    cout << "Max water: " << maxWater(h) << endl;  // 49
    return 0;
}

public class TwoPointersMore {

    static int removeDuplicates(int[] arr) {
        if (arr.length == 0) return 0;
        int slow = 0;
        for (int fast = 1; fast < arr.length; fast++) {
            if (arr[fast] != arr[slow]) {
                slow++;
                arr[slow] = arr[fast];
            }
        }
        return slow + 1;
    }

    static int maxWater(int[] height) {
        int lo = 0, hi = height.length - 1, maxArea = 0;
        while (lo < hi) {
            int area = Math.min(height[lo], height[hi]) * (hi - lo);
            maxArea = Math.max(maxArea, area);
            if (height[lo] < height[hi]) lo++;
            else hi--;
        }
        return maxArea;
    }

    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 2, 3, 4, 4};
        System.out.println("Unique count: " + removeDuplicates(arr));  // 4

        int[] h = {1, 8, 6, 2, 5, 4, 8, 3, 7};
        System.out.println("Max water: " + maxWater(h));  // 49
    }
}

# Remove duplicates from sorted array in-place � O(n)
def remove_duplicates(arr):
    if not arr: return 0
    slow = 0
    for fast in range(1, len(arr)):
        if arr[fast] != arr[slow]:
            slow += 1
            arr[slow] = arr[fast]
    return slow + 1

# Container With Most Water � O(n)
def max_water(height):
    lo, hi, max_area = 0, len(height) - 1, 0
    while lo < hi:
        area = min(height[lo], height[hi]) * (hi - lo)
        max_area = max(max_area, area)
        if height[lo] < height[hi]: lo += 1
        else: hi -= 1
    return max_area

arr = [1, 1, 2, 2, 3, 4, 4]
print("Unique count:", remove_duplicates(arr))  # 4

h = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print("Max water:", max_water(h))  # 49

# Three Sum � O(n�)
def three_sum(nums):
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]: continue  # skip duplicates
        lo, hi = i + 1, len(nums) - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s == 0:
                result.append([nums[i], nums[lo], nums[hi]])
                while lo < hi and nums[lo] == nums[lo + 1]: lo += 1
                while lo < hi and nums[hi] == nums[hi - 1]: hi -= 1
                lo += 1; hi -= 1
            elif s < 0: lo += 1
            else: hi -= 1
    return result

print(three_sum([-1, 0, 1, 2, -1, -4]))  # [[-1, -1, 2], [-1, 0, 1]]

// Remove duplicates from sorted array in-place
function removeDuplicates(arr) {
    if (!arr.length) return 0;
    let slow = 0;
    for (let fast = 1; fast < arr.length; fast++) {
        if (arr[fast] !== arr[slow]) {
            slow++;
            arr[slow] = arr[fast];
        }
    }
    return slow + 1;
}

// Container With Most Water
function maxWater(height) {
    let lo = 0, hi = height.length - 1, maxArea = 0;
    while (lo < hi) {
        const area = Math.min(height[lo], height[hi]) * (hi - lo);
        maxArea = Math.max(maxArea, area);
        if (height[lo] < height[hi]) lo++;
        else hi--;
    }
    return maxArea;
}

// Three Sum � O(n�)
function threeSum(nums) {
    nums.sort((a, b) => a - b);
    const result = [];
    for (let i = 0; i < nums.length - 2; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let lo = i + 1, hi = nums.length - 1;
        while (lo < hi) {
            const s = nums[i] + nums[lo] + nums[hi];
            if (s === 0) {
                result.push([nums[i], nums[lo], nums[hi]]);
                while (lo < hi && nums[lo] === nums[lo + 1]) lo++;
                while (lo < hi && nums[hi] === nums[hi - 1]) hi--;
                lo++; hi--;
            } else if (s < 0) lo++;
            else hi--;
        }
    }
    return result;
}

console.log(removeDuplicates([1,1,2,2,3,4,4]));          // 4
console.log(maxWater([1,8,6,2,5,4,8,3,7]));              // 49
console.log(threeSum([-1,0,1,2,-1,-4]));                  // [[-1,-1,2],[-1,0,1]]

Previous Next

Two Pointers Technique

What is the Two Pointers Technique?

When to Use Two Pointers

Remove Duplicates and Container With Most Water

Ready to Level Up Your Skills?