TWO POINTERS IN JAVA

The two pointers algorithm is a technique that uses two pointers to solve various types of problems in an array or list. These problems usually involve searching for pairs or subarrays with certain properties, such as finding a pair of numbers that sum to a specific value, or removing duplicates from a sorted array.

The basic idea is to have two pointers representing indices in the array. The pointers are often initialized at different positions (e.g., at the beginning and end of the array) and move towards each other based on certain conditions until they meet or cross.

Here’s a detailed example to illustrate the two pointers algorithm:

Example: Finding a Pair with a Given Sum in a Sorted Array

Given a sorted array of integers and a target sum, find a pair of numbers in the array that add up to the target sum.

Java Code

public class TwoPointersExample {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 6};
        int targetSum = 6;

        int[] result = findPairWithSum(arr, targetSum);

        if (result != null) {
            System.out.println("Pair found: (" + result[0] + ", " + result[1] + ")");
        } else {
            System.out.println("No pair found.");
        }
    }

    public static int[] findPairWithSum(int[] arr, int targetSum) {
        int left = 0;  // Start pointer
        int right = arr.length - 1;  // End pointer

        while (left < right) {
            int currentSum = arr[left] + arr[right];

            if (currentSum == targetSum) {
                return new int[] {arr[left], arr[right]};
            } else if (currentSum < targetSum) {
                left++;  // Move the left pointer to the right
            } else {
                right--;  // Move the right pointer to the left
            }
        }

        // If we reach here, then no pair was found
        return null;
    }
}

Explanation

1. Initialization: The two pointers, left and right, are initialized to the start (index 0) and end (last index) of the array, respectively.
2. Loop Condition: The loop runs as long as left is less than right. This ensures that the pointers do not cross each other.
3. Current Sum Calculation: Inside the loop, the sum of the elements at the left and right pointers (currentSum = arr[left] + arr[right]) is calculated.
4. Comparison with Target:

• If currentSum equals the targetSum, we have found a pair that satisfies the condition, so the pair is returned.
• If currentSum is less than the targetSum, it means we need a larger sum, so we move the left pointer to the right (left++) to increase the sum.
• If currentSum is greater than the targetSum, it means we need a smaller sum, so we move the right pointer to the left (right--) to decrease the sum.

1. No Pair Found: If the loop completes without finding a pair, null is returned to indicate that no such pair exists in the array.

This approach works efficiently with a time complexity of (O(n)) since each element is processed at most once by the two pointers. The two pointers algorithm can be adapted for various other problems involving arrays or linked lists.