Two Pointer Technique on Arrays in DSA Java - Execution Trace

Concept Flow - Two Pointer Technique on Arrays

Initialize two pointers: left=0, right=n-1

↓

Check condition: left < right?

No→Stop

Yes↓

Compare or process elements at left and right

↓

Move pointers: left++ or right-- or both

↩Back to condition check

Start with two pointers at array ends, compare or process elements, then move pointers inward until they meet or cross.

Execution Sample

DSA Java

int left = 0, right = arr.length - 1;
while (left < right) {
  if (arr[left] + arr[right] == target) {
    // found pair
    break;
  } else if (arr[left] + arr[right] < target) {
    left++;
  } else {
    right--;
  }
}

Find two numbers in a sorted array that add up to a target by moving two pointers inward.

Execution Table

Step	Operation	left	right	arr[left]	arr[right]	Sum	Action	Pointer Movement	Visual State
1	Initialize pointers	0	5	1	12	13	Check sum vs target	None	[1, 3, 4, 6, 8, 12]
2	Sum=13 > target=10	0	5	1	12	13	Sum too big	right--	[1, 3, 4, 6, 8, 12]
3	Move right pointer	0	4	1	8	9	Sum too small	left++	[1, 3, 4, 6, 8, 12]
4	Move left pointer	1	4	3	8	11	Sum too big	right--	[1, 3, 4, 6, 8, 12]
5	Move right pointer	1	3	3	6	9	Sum too small	left++	[1, 3, 4, 6, 8, 12]
6	Move left pointer	2	3	4	6	10	Sum equals target	Found pair	[1, 3, 4, 6, 8, 12]
7	Stop	2	3	4	6	10	Pair found, exit loop	None	[1, 3, 4, 6, 8, 12]

💡 Pointers met or pair found with sum equal to target

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
left	0	0	1	1	2	2	2
right	5	4	4	3	3	3	3
sum	13	9	11	9	10	10	10

Key Moments - 3 Insights

Why do we move the left pointer when the sum is less than the target?

Because the array is sorted, increasing the left pointer moves to a larger number, increasing the sum. See execution_table rows 3 and 5 where left++ happens after sum < target.

Why do we move the right pointer when the sum is greater than the target?

Because the array is sorted, decreasing the right pointer moves to a smaller number, decreasing the sum. See execution_table rows 2 and 4 where right-- happens after sum > target.

When does the loop stop if no pair is found?

The loop stops when left pointer is no longer less than right pointer (left >= right). See concept_flow and exit_note.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'left' after step 5?

A 2

B 1

C 3

D 0

💡 Hint

Check the 'left' column in execution_table row for step 5.

At which step does the sum equal the target?

A Step 4

B Step 6

C Step 3

D Step 2

💡 Hint

Look at the 'Sum' and 'Action' columns in execution_table.

If the array was not sorted, how would the pointer movement change?

A Pointers would move the same way

B Only right pointer would move

C We could not decide which pointer to move based on sum comparison

D Only left pointer would move

💡 Hint

Two pointer technique relies on sorted array to decide pointer movement, see key_moments.

Concept Snapshot

Two Pointer Technique on Arrays:
- Use two pointers at array ends (left=0, right=n-1)
- While left < right, compare or process arr[left] and arr[right]
- Move pointers inward based on condition (e.g., sum < target → left++, sum > target → right--)
- Stops when pointers meet or condition satisfied
- Requires sorted array for correct pointer movement

Full Transcript

The two pointer technique uses two indexes starting at opposite ends of a sorted array. We check the sum of elements at these pointers. If the sum is less than the target, we move the left pointer right to increase the sum. If the sum is greater, we move the right pointer left to decrease the sum. This continues until the pointers meet or we find the target sum. This method is efficient because it avoids checking all pairs by leveraging the sorted order. The execution table shows each step with pointer positions, values, sums, and actions taken. Key moments clarify why pointers move as they do and when the loop stops. The visual quiz tests understanding of pointer values and conditions during execution.

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