Why Two Pointer Technique on Arrays in DSA Java?

The Big Idea

What if you could find pairs in a list without checking every single combination?

The Scenario

Imagine you have a long list of numbers and you want to find two numbers that add up to a specific target. Doing this by checking every possible pair one by one feels like searching for a needle in a haystack.

The Problem

Checking every pair means lots of repeated work and takes a lot of time, especially if the list is very long. It's easy to make mistakes or miss pairs because you have to remember which pairs you already checked.

The Solution

The two pointer technique uses two markers that move through the list from different ends. This way, you can find pairs or solve problems by moving pointers smartly without checking every pair, saving time and effort.

Before vs After

✗ Before

for (int i = 0; i < arr.length; i++) {
  for (int j = i + 1; j < arr.length; j++) {
    if (arr[i] + arr[j] == target) {
      return true;
    }
  }
}

✓ After

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--;
}

What It Enables

This technique lets you solve problems involving pairs or ranges in arrays quickly and clearly, even when the list is very large.

Real Life Example

Think about finding two friends in a crowd whose combined height matches a certain number. Instead of asking everyone, you look from shortest and tallest ends and move inward to find the perfect pair faster.

Key Takeaways

Manual pair checking is slow and error-prone.

Two pointers move from both ends to find answers efficiently.

Great for problems involving pairs or sorted arrays.

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