Two-pointer technique in Data Structures Theory - Mini Project: Build & Apply

Understanding the Two-Pointer Technique

📖 Scenario: Imagine you have a list of numbers representing the ages of people waiting in line. You want to find pairs of people whose ages add up to a specific number, like 50. Using the two-pointer technique helps you do this efficiently.

🎯 Goal: Build a simple example that uses the two-pointer technique to find pairs of numbers in a sorted list that add up to a target sum.

📋 What You'll Learn

Create a sorted list of integers called ages with the values [18, 22, 25, 28, 30, 35, 40]

Create two pointers called left and right to track positions in the list

Use a while loop to move the pointers and find pairs that add up to the target sum

Add a variable called target_sum set to 50

💡 Why This Matters

🌍 Real World

The two-pointer technique is used in real life to quickly find pairs or groups that meet certain conditions, like matching people for activities or balancing budgets.

💼 Career

Understanding this technique is important for software developers and data analysts to write efficient code for searching and matching tasks.

1

Create the sorted list of ages

Create a list called ages with these exact values: [18, 22, 25, 28, 30, 35, 40]

Data Structures Theory

# Create the list of ages
# Your code here

Hint

Use square brackets to create a list and separate numbers with commas.

2

Set the target sum and initialize pointers

Create a variable called target_sum and set it to 50. Then create two variables called left and right. Set left to 0 and right to the last index of the ages list.

Data Structures Theory

ages = [18, 22, 25, 28, 30, 35, 40]
# Set target_sum and initialize left and right pointers
# Your code here

Hint

Use len(ages) - 1 to get the last index of the list.

3

Use a while loop to find pairs adding to the target sum

Write a while loop that runs as long as left is less than right. Inside the loop, calculate the sum of ages[left] and ages[right]. If the sum equals target_sum, move both pointers inward by increasing left by 1 and decreasing right by 1. If the sum is less than target_sum, increase left by 1. Otherwise, decrease right by 1.

Data Structures Theory

ages = [18, 22, 25, 28, 30, 35, 40]
target_sum = 50
left = 0
right = len(ages) - 1
# Use a while loop to move pointers and check sums
# Your code here

Hint

Remember to update the pointers based on the comparison of current_sum and target_sum.

4

Complete the logic to record pairs found

Create an empty list called pairs before the loop. Inside the if current_sum == target_sum block, add the tuple (ages[left], ages[right]) to pairs. This will store all pairs that add up to the target sum.

Data Structures Theory

ages = [18, 22, 25, 28, 30, 35, 40]
target_sum = 50
left = 0
right = len(ages) - 1
pairs = []
while left < right:
    current_sum = ages[left] + ages[right]
    if current_sum == target_sum:
        # Add the pair to pairs list
        # Your code here
        left += 1
        right -= 1
    elif current_sum < target_sum:
        left += 1
    else:
        right -= 1

Hint

Use the append() method to add pairs to the list.

Practice

1. What is the main purpose of the two-pointer technique in data structures?

easy

A. To store data in two separate arrays

B. To use two markers to scan data efficiently

C. To sort data using two different algorithms

D. To create two copies of the data for backup

Solution

1. Step 1: Recall the main purpose of the two-pointer technique

   The two-pointer technique uses two markers or pointers to scan through data efficiently, reducing unnecessary checks.

2. Step 2: Compare with other options

   The other options describe unrelated actions like storing data in separate arrays, sorting data, or creating backups, which are not the main purpose of this technique.

3. Final Answer:

   To use two markers to scan data efficiently -> Option B

4. Quick Check:

   Two-pointer technique = efficient scanning [OK]

Hint: Two pointers scan data fast by moving through it together [OK]

Common Mistakes:

• Confusing two-pointer with sorting algorithms
• Thinking it copies data instead of scanning
• Assuming it stores data separately

2. Which of the following is the correct way to initialize two pointers left and right for scanning an array arr from both ends?

easy

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

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

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

D. left = -1; right = len(arr) + 1

Solution

1. Step 1: Identify valid pointer positions

   For scanning from both ends, left starts at 0 (first index) and right at len(arr) - 1 (last index).

2. Step 2: Check other options for errors

   The other options use invalid indices like starting at 1 or beyond array length, which cause errors or miss elements.

3. Final Answer:

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

4. Quick Check:

   Start pointers at array ends = left = 0; right = len(arr) - 1 [OK]

Hint: Start left at 0 and right at last index for two-pointer scan [OK]

Common Mistakes:

• Starting pointers outside array bounds
• Using length instead of length minus one
• Swapping left and right initial values

3. Consider the following code using the two-pointer technique to check if a string is a palindrome:

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

print(is_palindrome('radar'))

What will be the output?

medium

A. True

B. None

C. Error

D. False

Solution

1. Step 1: Understand the palindrome check logic

   The code compares characters from the start and end moving inward. If any pair differs, it returns False; otherwise, True.

2. Step 2: Apply to 'radar'

   Characters match at all pairs: 'r'=='r', 'a'=='a', middle 'd' ignored. So, it returns True.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Palindrome check for 'radar' = True [OK]

Hint: Check characters from ends moving inward for palindrome [OK]

Common Mistakes:

• Confusing return values for palindrome
• Not updating pointers correctly
• Ignoring middle character in odd length strings

4. The following code attempts to find if there exists a pair in a sorted array arr that sums to target using the two-pointer technique:

def has_pair(arr, target):
    left, right = 0, len(arr)
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return True
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return False

What is the error in this code?

medium

A. The function should return True at the end

B. The loop condition should be while left <= right

C. The current_sum calculation is wrong

D. The right pointer is initialized incorrectly

Solution

1. Step 1: Check pointer initialization

   The right pointer is set to len(arr), which is outside valid index range (max index is len(arr)-1).

2. Step 2: Identify correct initialization

   Right pointer should be len(arr) - 1 to point to the last element.

3. Final Answer:

   The right pointer is initialized incorrectly -> Option D

4. Quick Check:

   Right pointer must be last index, not length [OK]

Hint: Right pointer = last index, not array length [OK]

Common Mistakes:

• Setting right pointer to array length
• Using wrong loop condition
• Miscomputing sum inside loop

5. You have two sorted arrays A and B. Using the two-pointer technique, how can you efficiently find all pairs (a, b) such that a + b = target? Choose the best approach.

hard

A. Use nested loops to check every pair from A and B

B. Sort both arrays again and then check pairs

C. Use one pointer on A starting at 0 and one on B starting at end, move pointers based on sum comparison

D. Use a hash map to store sums of all pairs

Solution

1. Step 1: Understand two-pointer approach for two sorted arrays

   Start pointer i at beginning of A and pointer j at end of B. Calculate sum A[i]+B[j].

2. Step 2: Move pointers based on sum

   If sum equals target, record pair and move pointers. If sum less than target, move i forward; if greater, move j backward. This avoids nested loops and is efficient.

3. Final Answer:

   Use one pointer on A starting at 0 and one on B starting at end, move pointers based on sum comparison -> Option C

4. Quick Check:

   Two-pointer on sorted arrays finds pairs efficiently [OK]

Hint: One pointer start, one pointer end; move based on sum [OK]

Common Mistakes:

• Using nested loops causing slow performance
• Resorting already sorted arrays unnecessarily
• Using hash map instead of two-pointer for sorted arrays