Two Pointer Technique on Arrays in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Two Pointer Technique on Arrays?

It is a method where two pointers start at different positions in an array and move towards each other or in the same direction to solve problems efficiently.

beginner

When is the Two Pointer Technique useful?

It is useful when you need to find pairs, triplets, or subarrays that satisfy certain conditions without using extra space or nested loops.

beginner

In the Two Pointer Technique, what do the pointers usually represent?

They usually represent indices in the array that move to check or compare elements to find a solution, like start and end positions.

intermediate

Example: How do two pointers help find if an array has two numbers that sum to a target?

Sort the array, set one pointer at start and one at end. Move pointers inward based on sum comparison until the target sum is found or pointers cross.

intermediate

What is a key advantage of the Two Pointer Technique over nested loops?

It reduces time complexity from O(n²) to O(n) by avoiding repeated comparisons and using linear scans with two pointers.

What is the initial position of pointers in the Two Pointer Technique for a sorted array to find two numbers summing to a target?

A Both at end

B One at start, one at end

C Both at start

D Random positions

One pointer starts at the beginning and the other at the end to check sums efficiently.

Which problem can be solved efficiently using the Two Pointer Technique?

A Finding pairs with a given sum

B Sorting an array

C Finding maximum element

D Calculating factorial

Two pointers help find pairs with a given sum in linear time after sorting.

What is the time complexity of the Two Pointer Technique on arrays?

A O(n log n)

B O(n²)

C O(log n)

D O(n)

Two pointers scan the array linearly, resulting in O(n) time complexity.

If the sum of elements at two pointers is less than the target, what should you do?

A Move the left pointer right

B Move the right pointer left

C Stop the search

D Move both pointers

Moving the left pointer right increases the sum in a sorted array.

Can the Two Pointer Technique be used on unsorted arrays directly?

A Only if array has unique elements

B Yes, always

C No, array must be sorted first

D Only for arrays with even length

Sorting is usually required to apply the two pointer technique for sum problems.

Explain how the Two Pointer Technique works to find two numbers in a sorted array that add up to a target.

Think about how moving pointers changes the sum.

Describe the advantages of using the Two Pointer Technique over nested loops for array problems.

Focus on performance and simplicity.

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