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

Recall & Review

beginner

What is the Two Pointer Technique on Arrays?

It is a method where two pointers move through the array to solve problems efficiently, often from different ends or at different speeds.

beginner

How do the two pointers usually move in the Two Pointer Technique?

They often start at opposite ends of the array and move towards each other, or one pointer moves faster than the other to find pairs or subarrays.

intermediate

Why is the Two Pointer Technique efficient compared to nested loops?

Because it reduces the time complexity from O(n²) to O(n) by avoiding repeated scanning of the array with nested loops.

beginner

Example problem: Find if there exists two numbers in a sorted array that add up to a target sum using Two Pointer Technique. What is the approach?

Start one pointer at the beginning and one at the end. If their sum is less than target, move the start pointer forward. If more, move the end pointer backward. Repeat until pointers meet or sum found.

intermediate

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

Usually no. The array often needs to be sorted first to use this technique effectively for problems like pair sums.

In the Two Pointer Technique, if the sum of elements at pointers is greater than the target, what should you do?

A Move the pointer at the end backward

B Move the pointer at the start forward

C Stop the process

D Move both pointers forward

If the sum is too big, moving the end pointer backward reduces the sum.

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

A O(log n)

B O(n log n)

C O(n²)

D O(n)

Two pointers move through the array once, so time complexity is O(n).

Which condition is usually required to apply the Two Pointer Technique for pair sum problems?

A Array must be empty

B Array must be sorted

C Array must have only positive numbers

D Array must be unsorted

Sorting helps pointers decide which way to move based on sum comparisons.

If two pointers start at the beginning of the array and move at different speeds, what problem can this solve?

A Finding duplicates

B Sorting the array

C Detecting cycles in linked lists

D Reversing the array

Slow and fast pointers are used in linked lists to detect cycles by moving at different speeds.

What happens when the two pointers meet in the Two Pointer Technique?

A The search ends

B You must reset pointers

C You double the pointers

D You ignore the meeting

When pointers meet, it means all pairs or elements have been checked.

Explain the Two Pointer Technique and how it helps solve array problems efficiently.

Think about how two markers move through the array to find pairs or subarrays.

Describe a step-by-step approach to find two numbers in a sorted array that add up to a target using the Two Pointer Technique.

Imagine walking from both ends of a hallway to find two people whose heights add up to a number.

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