Two-Pointer Technique

Introduction

• The two-pointer technique is essential for software developers, especially in technical interviews.
• It uses two variables (or pointers) to track indexes in arrays or strings, which helps save time and space.

What are Pointers?

• A pointer is a reference to an object that stores a memory address of another value in computer memory.
• Can be as simple as a variable referencing an index or as complex as pointing to nodes in data structures.

When to Use Two Pointers

• Useful for analyzing each element of a collection in relation to others.
• Allows processing of two elements per loop iteration, optimizing performance.

Types of Two-Pointer Patterns

1. Two pointers moving inward:
   • Both pointers start at the ends of the array and move toward each other.
2. Slow and Fast pointers:
   • One pointer (slow) moves one step, while the other (fast) moves two steps.

Example: Two Sum Problem

• Problem Statement: Given a sorted array, find two elements that add up to a target number.
• Naive Approach: Iterate through the entire array pairwise, leading to O(n²) time complexity.
• Optimized Approach with Two Pointers:
  • Set pointer 1 to the first element (index 0) and pointer 2 to the last element (length - 1).
  • While pointer 1 < pointer 2, check the sum of elements at these pointers:
    • If the sum equals the target, return true.
    • If the sum is less, move pointer 1 forward.
    • If the sum is more, move pointer 2 backward.

Example: Cycle Detection in Linked Lists

• Problem Statement: Detect if a cycle exists in a linked list.
• Method: Use slow and fast pointers:
  • Slow pointer moves one step, fast pointer moves two steps.
  • If they meet, a cycle exists; if fast reaches the end, no cycle exists.

Summary

• The two-pointer technique is a powerful tool for efficiently solving problems related to arrays, strings, and linked lists.
• Understanding when and how to implement it can greatly improve algorithm performance.