Two-pointer technique in Data Structures Theory - Full Explanation

Introduction

Imagine you need to find pairs or sections in a list that meet certain conditions quickly. Checking every possibility one by one can take a long time. The two-pointer technique helps solve such problems efficiently by using two markers moving through the list.

Explanation

Basic idea

The two-pointer technique uses two markers, or pointers, that start at different positions in a list or array. These pointers move towards each other or in the same direction to find pairs or subarrays that satisfy a condition. This avoids checking every pair individually.

Two pointers reduce the number of checks by moving through the list strategically.

Common uses

This technique is often used to find pairs with a given sum, remove duplicates, or find subarrays with certain properties. It works best when the list is sorted or when the problem allows linear scanning with two markers.

Two-pointer technique is useful for problems involving pairs or continuous sections in lists.

Pointer movement

Depending on the problem, pointers can move towards each other from opposite ends or move forward together. The movement depends on comparing values at pointers and adjusting them to meet the problem's condition.

Pointer movement is guided by problem conditions to efficiently narrow down the search.

Efficiency advantage

By using two pointers, the algorithm often runs in linear time, O(n), instead of quadratic time, O(n²), which happens when checking all pairs. This makes it much faster for large lists.

Two-pointer technique improves efficiency by reducing time complexity to linear.

Real World Analogy

Imagine two people starting at opposite ends of a long hallway looking for matching pairs of shoes. They walk towards each other, comparing shoes as they go, and decide whether to move forward or backward based on what they find. This way, they find pairs faster than checking every shoe with every other shoe.

Basic idea → Two people starting at opposite ends of a hallway

Common uses → Looking for matching pairs of shoes or groups in the hallway

Pointer movement → People deciding to move closer or step back based on shoe matches

Efficiency advantage → Finding pairs faster than checking every shoe with every other shoe

Diagram

Diagram

Start of list
┌─────────────┐
│ 1  3  4  6  8  9  11 │
└─────────────┘
  ↑                       ↑
 left pointer         right pointer

Pointers move towards each other to find pairs.

Diagram shows two pointers at opposite ends of a sorted list moving towards each other.

Key Facts

Two-pointer technique → An algorithmic approach using two markers moving through a list to solve problems efficiently.

Pointer → A marker or index used to track a position in a list or array.

Linear time complexity → An algorithm runs in linear time if its steps grow proportionally with input size.

Sorted list → A list arranged in ascending or descending order.

Code Example

Data Structures Theory

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return (left, right)
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return None

# Example usage
nums = [1, 3, 4, 6, 8, 9, 11]
target = 10
result = two_sum_sorted(nums, target)
print(result)

Common Confusions

Two-pointer technique only works on sorted lists.

Two-pointer technique only works on sorted lists. While it works best on sorted lists, it can also be applied to unsorted lists if the problem allows moving pointers based on conditions.

Pointers always move towards each other.

Pointers always move towards each other. Pointers can move in the same direction or towards each other depending on the problem's needs.

Summary

Two-pointer technique uses two markers moving through a list to solve problems faster than checking all pairs.

It works best on sorted lists but can be adapted to other cases depending on problem rules.

This technique often reduces time complexity from quadratic to linear, making it efficient for large inputs.

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