NUHMAN.com

Two-Pointer Technique in Java

The two-pointer technique is a popular strategy for solving problems that involve searching pairs or ranges in arrays or linked lists. It typically uses two indices moving towards each other, making it highly efficient for sorted data.

🧠 Problem Example: Find a Pair with a Given Sum

Task:

Given a sorted array, find the two indices of elements that sum to a target value.

🪜 Steps

1. Initialize Two Pointers:

• left at the start of the array.
• right at the end of the array.

1. Loop While left < right:

• Calculate sum = nums[left] + nums[right].
• If sum == target, return indices.
• If sum < target, move left pointer right to increase the sum.
• If sum > target, move right pointer left to decrease the sum.

1. Stop When Pointers Cross:

• If no pair found, return -1, -1.

✅ Java Implementation

java

public class TwoPointersExample {
    public static int[] findPairWithSum(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int sum = nums[left] + nums[right];

            if (sum == target) {
                return new int[]{left, right};
            } else if (sum < target) {
                left++; // Move left to the right to increase sum
            } else {
                right--; // Move right to the left to decrease sum
            }
        }

        return new int[]{-1, -1}; // No pair found
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 6, 8, 9};
        int target = 10;

        int[] result = findPairWithSum(nums, target);

        if (result[0] != -1) {
            System.out.println("Pair found at indices: " + result[0] + " and " + result[1]);
        } else {
            System.out.println("No pair found with the given sum.");
        }
    }
}

🧪 Example Output

yaml

Pair found at indices: 1 and 6

Explanation: nums[1] + nums[6] = 2 + 8 = 10 ✅

🧩 Key Concepts

• Time Complexity: O(n) — Single pass through the array.
• Space Complexity: O(1) — Constant extra space.
• Prerequisite: Array must be sorted for this approach to work.
• Applications:
• Pair sums
• Palindrome checks
• Merging sorted arrays
• Trapping rainwater problems
• Removing duplicates in-place

🚀 Bonus Tip

For unsorted arrays, sort the array first (O(n log n)), then apply the two-pointer method.