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).

• 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");
      }
  }

  Output:

  Pair found at 1 and 3 index positions

• 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] + " ");
          }
      }
  }

  Output:

  Array after removing duplicates: 1 2 3 4 5

Two-Pointers Technique Task:

Try to solve the following problems using the Two Pointers Technique:

1. WAP to Move Zeros to End of an Array
2. WAP to Find Triplet with Given Sum in a Sorted Array
3. WAP to Check if an Array is Palindrome
4. WAP to Find Maximum Water Container