🎉 Festival Deal: Save Big on Professional Courses with Real Projects – Apply Coupons FEST300OFF FEST500OFF
→ Click Here ←

Two Pointers Technique  


Introduction
  • The Two Pointers Technique is a problem-solving strategy where we use two variables (pointers) to traverse an array, string, or linked list from different directions or at different speeds.
  • Its goal is to reduce time complexity by avoiding nested loops and processing data in O(n) instead of O(n²).
  • Types of Movement:
    • Opposite Direction: One pointer starts from the beginning, another from the end (e.g., Two Sum in sorted array etc).
    • Same Direction: Both pointers start from the beginning, one moves faster/slower (e.g., Remove Duplicates, Sliding Window etc).
  • Two Pointers Approach in Java DSA

  • Advantages:
    • Better Time Complexity: Often reduces from O(n²)O(n) or O(n log n).
    • Space Efficient: Works with constant extra space (O(1)).
    • Simpler Logic: Easy to implement once we understand the pattern.
    • Versatile: Can be applied to arrays, strings, and linked lists.
  • When to Use:
    Use Two Pointers Technique when:
    • The array/string is sorted (most common case).
    • We have linear data structures like arrays, strings, linked lists etc.
    • We want to optimize nested loops (avoid brute force O(n²)).
    • We are working with subarrays/substrings (sliding window is an extension of this).
    • We need to find a pair, triplet or subarray satisfying a condition (sum, difference, etc.).
    • We want to minimize/maximize something (window size, distance).
Programs:-
  • Program 1: Two Sum in Sorted Array (Using Opposite Direction)
    public class MainApp1
    {
        public static void main(String[] args)
        {
            int[] arr = {2, 3, 4, 7, 11, 15};
            int target = 10;
    
            int left = 0, right = arr.length - 1;
            boolean found = false;
    
            while (left < right)
            {
                int sum = arr[left] + arr[right];
    
                if (sum == target)
                {
                    System.out.println("Pair found at "+left+" and "+right+" index positions");
                    found = true;
                    break;
                }
                else if (sum < target)
                {
                    left++;  // Move left pointer forward
                }
                else
                {
                    right--; // Move right pointer backward
                }
            }
    
            if (!found)
                System.out.println("No pair found");
        }
    }
  • Program 2: Remove duplicates from sorted array
    public class MainApp2
    {
        public static void main(String[] args)
        {
            int[] arr = {1, 1, 2, 2, 3, 3, 4, 5};
            int n = arr.length;
    
            int left = 0;  // points to last unique element
            int right = 1; // used to scan the array
    
            while (right < n)
            {
                if (arr[right] != arr[left])
                {
                    left++;            // move left to next position
                    arr[left] = arr[right];  // place unique element at left
                }
                right++;  // always move right pointer
            }
    
            // Print unique elements (first left+1 elements are unique)
            System.out.print("Array after removing duplicates: ");
            for (int i = 0; i <= left; i++)
            {
                System.out.print(arr[i] + " ");
            }
        }
    }

Other Programs:

Here are some popular problems solved using Two Pointers:

  1. Move Zeros to End of an array
  2. Find triplet with given sum in sorted array
  3. Check if array is palindrome
  4. Find maximum water container