Two Pointer Technique on Arrays in DSA Java - Build from Scratch

Two Pointer Technique on Arrays

📖 Scenario: You are helping a friend organize their collection of numbered cards. The cards are arranged in a line, and you want to find two cards that add up to a specific number.

🎯 Goal: Build a program that uses the two pointer technique to find if there are two numbers in a sorted array that add up to a target sum.

📋 What You'll Learn

Create an integer array called cards with the exact values {1, 3, 4, 5, 7, 10, 12}

Create an integer variable called targetSum and set it to 9

Use two pointers named left and right to find if any two numbers in cards add up to targetSum

Print "Found a pair: x and y" if such a pair exists, where x and y are the numbers

If no pair is found, print "No pair found"

💡 Why This Matters

🌍 Real World

Finding pairs of numbers that add up to a target is useful in budgeting, shopping discounts, and matching items in inventory.

💼 Career

Two pointer technique is a common pattern in coding interviews and helps solve problems efficiently without extra space.

1

Create the cards array

Create an integer array called cards with these exact values: {1, 3, 4, 5, 7, 10, 12}

DSA Java

// Your code here

Hint

Use int[] cards = {1, 3, 4, 5, 7, 10, 12}; to create the array.

2

Add the targetSum variable

Create an integer variable called targetSum and set it to 9 inside the main method after the cards array

DSA Java

public class TwoPointer {
    public static void main(String[] args) {
        int[] cards = {1, 3, 4, 5, 7, 10, 12};
        // Your code here
    }
}

Hint

Use int targetSum = 9; to create the target sum variable.

3

Use two pointers to find the pair

Use two integer pointers called left and right initialized to the start and end of cards respectively. Use a while loop to check if the sum of cards[left] and cards[right] equals targetSum. If the sum is less, move left forward. If the sum is more, move right backward. Stop when left is not less than right. Inside the loop, if you find the pair, break out of the loop.

DSA Java

public class TwoPointer {
    public static void main(String[] args) {
        int[] cards = {1, 3, 4, 5, 7, 10, 12};
        int targetSum = 9;
        // Your code here
    }
}

Hint

Use left and right pointers and a while loop to find the pair.

4

Print the result

After the loop, use an if statement to check the boolean variable found. If true, print "Found a pair: " followed by cards[left] and cards[right]. Otherwise, print "No pair found".

DSA Java

public class TwoPointer {
    public static void main(String[] args) {
        int[] cards = {1, 3, 4, 5, 7, 10, 12};
        int targetSum = 9;
        int left = 0;
        int right = cards.length - 1;
        boolean found = false;
        while (left < right) {
            int sum = cards[left] + cards[right];
            if (sum == targetSum) {
                found = true;
                break;
            } else if (sum < targetSum) {
                left++;
            } else {
                right--;
            }
        }
        // Your code here
    }
}

Hint

Use System.out.println to print the result based on found.

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