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:
  1. Opposite Direction :
  In this approach, one pointer starts at the beginning of the array and the other at the end. They move towards each other based on certain conditions.
  

  2. Same Direction :
  Here, both pointers start at the beginning of the array and move forward at different speeds or steps to find subarrays or pairs.

  3. Independent Direction :
  In this type, both pointers can move in any direction independently based on specific conditions.

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

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 (Using Same Direction)

  public class MainApp2
  {
      public static void main(String[] args)
      {
          int[] nums = {1, 1, 2, 2, 3, 3, 4, 5};
          int n = nums.length;
  
          int left = 0; // last unique element position
  
          // Two pointers: right scans, left writes unique values
          for (int right = 1; right < n; right++)
          {
              if (nums[left] != nums[right])
              {
                  left++;                     // move left forward
                  nums[left] = nums[right];   // copy unique element
              }
          }
  
          // Print unique elements (from index 0 to left)
          System.out.print("Array after removing duplicates: ");
          for (int i = 0; i <= left; i++)
          {
              System.out.print(nums[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