Two Pointer Technique on Arrays in DSA Java

Mental Model

Use two markers moving through the array to find or compare elements efficiently without extra space.

Analogy: Imagine two friends starting at opposite ends of a hallway, walking towards each other to find a meeting point or check something along the way.

Array: [1] -> [2] -> [3] -> [4] -> [5] -> null
Pointers: left ↑                             right ↑

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9], find if there is a pair that sums to 12

Goal: Find two numbers in the array that add up to 12 using two pointers

Step 1: Initialize left pointer at index 0 (value 1) and right pointer at index 4 (value 9)

[1] ↑ -> [3] -> [5] -> [7] -> [9] ↑

Why: Start checking pairs from the two ends of the array

Step 2: Calculate sum = 1 + 9 = 10, which is less than 12, so move left pointer right

[1] -> [3] ↑ -> [5] -> [7] -> [9] ↑

Why: Sum too small, need a bigger number, so move left pointer forward

Step 3: Calculate sum = 3 + 9 = 12, found the pair that sums to 12

[1] -> [3] ↑ -> [5] -> [7] -> [9] ↑

Why: Sum matches target, so we found the pair

Result:

Final pointers at indices 1 and 4 with values 3 and 9
Answer: Pair found (3, 9)

Annotated Code

DSA Java

public class TwoPointerSum {
    public static boolean hasPairWithSum(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            int sum = arr[left] + arr[right];
            if (sum == target) {
                return true; // found the pair
            } else if (sum < target) {
                left++; // increase sum by moving left pointer right
            } else {
                right--; // decrease sum by moving right pointer left
            }
        }
        return false; // no pair found
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int target = 12;
        boolean result = hasPairWithSum(arr, target);
        System.out.println("Pair found: " + result);
    }
}

while (left < right) {

loop until pointers meet to check all pairs

int sum = arr[left] + arr[right];

calculate sum of elements at pointers

if (sum == target) { return true; }

found pair matching target sum

else if (sum < target) { left++; }

sum too small, move left pointer right to increase sum

else { right--; }

sum too large, move right pointer left to decrease sum

Output

Pair found: true

Complexity Analysis

Time: O(n) because each pointer moves at most n steps through the array once

Space: O(1) because no extra space is used besides pointers

vs Alternative: Compared to nested loops O(n^2), two pointer reduces time by scanning array only once

Edge Cases

empty array

returns false immediately as no pairs exist

DSA Java

while (left < right) {

array with one element

returns false because at least two elements are needed

DSA Java

while (left < right) {

no pair sums to target

returns false after pointers cross without finding pair

DSA Java

return false; // no pair found

When to Use This Pattern

When you need to find pairs or compare elements from both ends of a sorted array efficiently, use two pointers to reduce time from quadratic to linear.

Common Mistakes

Mistake: Not moving pointers correctly when sum is less or greater than target
Fix: Move left pointer right if sum is less than target, move right pointer left if sum is greater

Summary

Find pairs in a sorted array efficiently using two pointers moving inward.

Use when searching pairs or conditions involving two elements in sorted arrays.

Two pointers from opposite ends let you check sums without nested loops.

Practice

1. What is the main idea behind the Two Pointer Technique when used on arrays?

easy

A. Use a single pointer to iterate through the array

B. Use two indices to traverse the array from different ends or positions simultaneously

C. Use recursion to divide the array into halves

D. Sort the array before processing

Solution

1. Step 1: Understand the technique's approach

   The two pointer technique uses two indices or pointers to scan the array from different positions, often from start and end.

2. Step 2: Compare with other options

   Sorting or recursion are different techniques; single pointer is not two pointer technique.

3. Final Answer:

   Use two indices to traverse the array from different ends or positions simultaneously -> Option B

4. Quick Check:

   Two pointers = two indices moving [OK]

Hint: Two pointers move from different sides or positions [OK]

Common Mistakes:

• Confusing with sorting or recursion
• Thinking it uses only one pointer
• Assuming it always requires sorted arrays

2. Which of the following is the correct syntax to initialize two pointers left and right for an array arr in Java?

easy

A. int left = arr.length, right = 0;

B. int left = 1, right = arr.length;

C. int left = 0, right = arr.length - 1;

D. int left = -1, right = arr.length + 1;

Solution

1. Step 1: Identify valid pointer initialization

   In Java, array indices start at 0 and end at length-1, so left = 0 and right = arr.length - 1 is correct.

2. Step 2: Check other options for invalid indices

   Options B, C, and D use invalid indices outside array bounds.

3. Final Answer:

   int left = 0, right = arr.length - 1; -> Option C

4. Quick Check:

   Start at 0 and end at length-1 [OK]

Hint: Array indices start at 0, end at length-1 [OK]

Common Mistakes:

• Using 1-based indexing
• Setting pointers outside array bounds
• Confusing length with last index

3. What will be the output of the following Java code snippet?

int[] arr = {1, 3, 5, 7, 9};
int left = 0, right = arr.length - 1;
int sum = 0;
while (left < right) {
    sum += arr[left] + arr[right];
    left++;
    right--;
}
System.out.println(sum);

medium

A. 15

B. 30

C. 25

D. 20

Solution

1. Step 1: Trace the loop iterations and sum calculation

   Initial pointers: left=0, right=4 - Iteration 1: sum=0+(1+9)=10, left=1, right=3 - Iteration 2: sum=10+(3+7)=20, left=2, right=2 Loop stops as left is not less than right.

2. Step 2: Final sum value

   Sum after loop is 20.

3. Final Answer:

   20 -> Option D

4. Quick Check:

   Sum pairs (1+9) + (3+7) = 20 [OK]

Hint: Add pairs from ends until pointers meet [OK]

Common Mistakes:

• Including middle element when left == right
• Adding elements multiple times
• Incorrect pointer updates

4. Identify the error in the following Java code using two pointers:

int[] arr = {2, 4, 6, 8};
int left = 0, right = arr.length;
while (left < right) {
    System.out.print(arr[left] + ",");
    left++;
    right--;
}

medium

A. The 'right' pointer is initialized out of array bounds

B. The loop condition should be 'left <= right'

C. The array should be sorted before using two pointers

D. The print statement should be outside the loop

Solution

1. Step 1: Check pointer initialization

   Array indices go from 0 to length-1, but right is set to arr.length, which is out of bounds.

2. Step 2: Validate other options

   Loop condition and print placement are valid; sorting is not required here.

3. Final Answer:

   The 'right' pointer is initialized out of array bounds -> Option A

4. Quick Check:

   Right pointer must be arr.length - 1 [OK]

Hint: Right pointer must be last valid index (length-1) [OK]

Common Mistakes:

• Setting right = arr.length instead of arr.length - 1
• Confusing loop conditions
• Assuming sorting is always needed

5. Given a sorted array arr and a target sum target, which two-pointer approach correctly finds if there exists a pair of numbers that add up to target?

int left = 0, right = arr.length - 1;
while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == target) {
        return true;
    } else if (sum < target) {
        left++;
    } else {
        right--;
    }
}
return false;

hard

A. Move left pointer right if sum is less than target, else move right pointer left

B. Always move left pointer right regardless of sum

C. Always move right pointer left regardless of sum

D. Move pointers randomly until sum matches

Solution

1. Step 1: Understand pointer movement logic

   If sum is less than target, increase sum by moving left pointer right; if sum is more, decrease sum by moving right pointer left.

2. Step 2: Confirm correctness of approach

   This approach works because array is sorted, so moving pointers adjusts sum towards target.

3. Final Answer:

   Move left pointer right if sum is less than target, else move right pointer left -> Option A

4. Quick Check:

   Adjust pointers based on sum vs target [OK]

Hint: Move pointers based on sum comparison with target [OK]

Common Mistakes:

• Moving pointers without checking sum
• Ignoring array sorted property
• Moving both pointers at once