Two Pointer Technique on Arrays in DSA Python - Execution Trace

Concept Flow - Two Pointer Technique on Arrays

Initialize two pointers: left=0, right=end

↓

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, move pointers inward until they meet or cross.

Execution Sample

DSA Python

arr = [1, 3, 5, 7, 9]
left, right = 0, 4
while left < right:
    print(arr[left], arr[right])
    left += 1
    right -= 1

Print pairs of elements from the start and end moving towards the center.

Execution Table

Step	Operation	left	right	Elements Compared	Pointer Movement	Array State
1	Initialize pointers	0	4	N/A	N/A	[1, 3, 5, 7, 9]
2	Check condition left < right	0	4	N/A	Condition True	[1, 3, 5, 7, 9]
3	Compare elements	0	4	1 and 9	N/A	[1, 3, 5, 7, 9]
4	Move pointers	1	3	N/A	left++ and right--	[1, 3, 5, 7, 9]
5	Check condition left < right	1	3	N/A	Condition True	[1, 3, 5, 7, 9]
6	Compare elements	1	3	3 and 7	N/A	[1, 3, 5, 7, 9]
7	Move pointers	2	2	N/A	left++ and right--	[1, 3, 5, 7, 9]
8	Check condition left < right	2	2	N/A	Condition False	[1, 3, 5, 7, 9]

💡 Pointers met at index 2, condition left < right is False, loop ends.

Variable Tracker

Variable	Start	After Step 4	After Step 7	Final
left	0	1	2	2
right	4	3	2	2

Key Moments - 3 Insights

Why does the loop stop when left equals right?

Because the condition left < right becomes False at step 8, meaning pointers have met or crossed, so no more pairs to compare.

What happens if we move only one pointer instead of both?

The pointers won't move towards each other properly, causing incorrect or incomplete processing, as shown by pointer movements at steps 4 and 7.

Why do we compare elements at left and right pointers?

Because the two pointer technique processes pairs from opposite ends, as seen in steps 3 and 6 where elements at left and right are compared.

Visual Quiz - 3 Questions

Look at the execution table, what are the elements compared at step 6?

A 3 and 7

B 5 and 5

C 1 and 9

D 7 and 3

💡 Hint

Check the 'Elements Compared' column at step 6 in the execution table.

At which step does the condition left < right become False?

A Step 4

B Step 7

C Step 8

D Step 3

💡 Hint

Look at the 'Pointer Movement' and 'Operation' columns for condition checks in the execution table.

If we only increment left pointer and never decrement right, what happens to the loop?

A It stops earlier

B It runs infinitely or misses pairs

C It compares all pairs correctly

D It reverses the array

💡 Hint

Refer to key moment about pointer movement and how both pointers must move inward.

Concept Snapshot

Two Pointer Technique on Arrays:
- Use two pointers starting at array ends (left=0, right=end).
- While left < right, process elements at pointers.
- Move pointers inward (left++, right--) each step.
- Stops when pointers meet or cross.
- Efficient for pairwise processing without extra space.

Full Transcript

The two pointer technique uses two indexes starting at opposite ends of an array. We check if the left pointer is less than the right pointer to continue. At each step, we compare or process the elements at these pointers. Then, we move the left pointer forward and the right pointer backward. This continues until the pointers meet or cross, meaning all pairs have been processed. This method is efficient for problems needing pairwise checks or processing from both ends without extra memory.

Practice

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

easy

A. Use two arrays to store temporary results

B. Sort the array twice before processing

C. Use two indices to scan the array from different ends or positions simultaneously

D. Use recursion to divide the array into two parts

Solution

1. Step 1: Understand the two pointer concept

   The technique uses two pointers (indices) to traverse the array, often starting from opposite ends or different positions.

2. Step 2: Recognize the purpose

   This helps solve problems efficiently by reducing the number of iterations compared to nested loops.

3. Final Answer:

   Use two indices to scan the array from different ends or positions simultaneously -> Option C

4. Quick Check:

   Two pointers scan array ends or positions [OK]

Hint: Think of two fingers moving inward or outward on the array [OK]

Common Mistakes:

• Confusing two pointers with using two separate arrays
• Assuming sorting is always required
• Thinking recursion is part of two pointer technique

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

easy

A. left = 0; right = len(arr) - 1

B. left = 1; right = len(arr)

C. left = -1; right = len(arr)

D. left = 0; right = len(arr)

Solution

1. Step 1: Identify valid pointer positions

   In Python, array indices start at 0, so the left pointer should start at 0.

2. Step 2: Set right pointer correctly

   The right pointer should be at the last valid index, which is length of array minus 1.

3. Final Answer:

   left = 0; right = len(arr) - 1 -> Option A

4. Quick Check:

   Start left at 0 and right at last index [OK]

Hint: Remember Python arrays start at 0, last index is length-1 [OK]

Common Mistakes:

• Setting right pointer to len(arr) causes index error
• Starting left pointer at 1 misses first element
• Using negative indices incorrectly

3. What will be the output of the following Python code?

arr = [1, 3, 5, 7, 9]
left, right = 0, 4
result = []
while left < right:
    result.append(arr[left] + arr[right])
    left += 1
    right -= 1
print(result)

medium

A. [10, 14]

B. [10, 12]

C. [10, 12, 14]

D. [10, 10]

Solution

1. Step 1: Trace the loop iterations

   Initial pointers: left=0, right=4 - Iteration 1: arr[0]+arr[4] = 1+9=10, result=[10] - left=1, right=3 - Iteration 2: arr[1]+arr[3] = 3+7=10, result=[10,10] - left=2, right=2 (loop ends because left is not less than right)

2. Step 2: Check loop condition and final result

   Loop stops when left == right (2), so only two sums added: [10, 10]

3. Final Answer:

   [10, 10] -> Option D

4. Quick Check:

   Sum pairs from ends until pointers meet [OK]

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

Common Mistakes:

• Including middle element sum when pointers meet
• Not updating pointers correctly
• Confusing indices causing wrong sums

4. Find the error in the following code that uses two pointers to check if an array is a palindrome:

def is_palindrome(arr):
    left, right = 0, len(arr)
    while left < right:
        if arr[left] != arr[right]:
            return False
        left += 1
        right -= 1
    return True

print(is_palindrome([1, 2, 3, 2, 1]))

medium

A. left should start at 1

B. right should be initialized as len(arr) - 1

C. Use 'while left <= right' instead of 'while left < right'

D. Return True should be inside the loop

Solution

1. Step 1: Check pointer initialization

   In Python, last index is len(arr) - 1, but code sets right = len(arr), which is out of range.

2. Step 2: Correct pointer initialization

   Change right to len(arr) - 1 to avoid index error and correctly compare elements.

3. Final Answer:

   right should be initialized as len(arr) - 1 -> Option B

4. Quick Check:

   Last index = length - 1 [OK]

Hint: Last index is length minus one, not length [OK]

Common Mistakes:

• Setting right pointer to length causes index error
• Changing loop condition incorrectly
• Returning True too early inside loop

5. Given a sorted array arr and a target sum target, how can you use the two pointer technique to find if there exists two numbers that add up to target? Choose the correct approach.

hard

A. Initialize left at 0 and right at len(arr)-1; move pointers inward based on sum comparison

B. Initialize both pointers at 0 and move right pointer only

C. Sort the array again and use binary search for each element

D. Use two nested loops to check all pairs

Solution

1. Step 1: Set pointers at array ends

   Start left pointer at 0 (start) and right pointer at last index (len(arr)-1).

2. Step 2: Move pointers based on sum

   Calculate sum of arr[left] + arr[right]. If sum equals target, return True. If sum is less, move left pointer right to increase sum. If sum is more, move right pointer left to decrease sum.

3. Final Answer:

   Initialize left at 0 and right at len(arr)-1; move pointers inward based on sum comparison -> Option A

4. Quick Check:

   Two pointers from ends adjust to find target sum [OK]

Hint: Move left/right pointers based on sum compared to target [OK]

Common Mistakes:

• Moving only one pointer without condition
• Using nested loops instead of two pointers
• Not starting pointers at array ends