What is Two Pointers coding pattern?

The Two Pointers pattern is a common algorithmic technique used primarily to simplify problems that involve arrays or linked lists. This technique uses two pointers that either move towards each other, away from each other, or in a synchronous manner, to scan the array or list in one or two passes.

Key Characteristics:

1. Efficiency: Typically reduces the time complexity from O(N²) to O(N).
2. Simplicity: Helps simplify the solution by eliminating the need for nested loops or complex data structures.

Common Use Cases:

• Pair sums in an array.
• Finding the closest pair in two sorted arrays.
• Reversing linked lists or arrays.
• Fast and slow pointer problems (e.g., detecting cycles in a linked list).

Example in Python:

Here's a Python example demonstrating the Two Pointers pattern, used to reverse an array:

def reverseArray(arr):
    left, right = 0, len(arr) - 1

    while left < right:
        # Swap elements
        arr[left], arr[right] = arr[right], arr[left]

        # Move pointers
        left += 1
        right -= 1

    return arr

# Example usage
arr = [1, 2, 3, 4, 5]
print("Reversed array:", reverseArray(arr))

In this example, left and right are the two pointers. The left pointer starts at the beginning of the array, and right starts at the end. They move towards each other, and as they progress, they swap the elements they point to. This continues until they meet or cross each other, resulting in a reversed array.

This pattern is efficient because it only scans the array once and does not require any extra space, unlike approaches that might involve creating a new array or using recursive calls.

Top types of problems well-suited for Two Pointers

The Two Pointers technique is particularly effective for solving array and linked list problems where you need to scan the elements, often to find a pair of values meeting certain criteria or to rearrange the elements in some way. Here are common types of problems well-suited for the Two Pointers approach:

1. Pair Sum Problems:

   • Finding pairs in an array that sum up to a specific target.
   • Example: "Find all pairs in an array that sum up to a given value."

2. Removing Duplicates:

   • Removing duplicates from a sorted array or linked list.
   • Example: "Remove duplicates from a sorted array."

3. Merging Two Sorted Arrays:

   • Merging two sorted arrays into a single sorted array.
   • Example: "Merge two sorted arrays."

4. Reversing a Sequence:

   • Reversing arrays or linked lists.
   • Example: "Reverse the elements of an array."

5. Cycle Detection in a Linked List:

   • Detecting cycles in a linked list using the fast and slow pointer technique.
   • Example: "Check if a linked list has a cycle."

6. Sliding Window Maximum/Minimum:

   • Finding the maximum/minimum value in a sliding window moving through the array.
   • Example: "Find the maximum sum of any contiguous subarray of size k."

7. Binary Search on Sorted Arrays:

   • Performing binary search or variations of it in a sorted array.
   • Example: "Find the start and end position of a given target value in a sorted array."

8. Palindrome or Valid Palindrome Check:

   • Checking if a string is a palindrome.
   • Example: "Determine if a given string is a palindrome."

9. Finding a Subarray with a Given Sum in an Array:

   • Finding a contiguous subarray that sums to a specific target.
   • Example: "Find a contiguous subarray that sums to k."

10. Comparing Strings:

• Comparing two strings, possibly to check for anagrams.
• Example: "Check if one string is an anagram of another."

The Two Pointers technique is chosen for its efficiency in solving these problems, often reducing time complexity significantly. It allows for a linear time solution, avoiding the need for nested loops, which would result in higher time complexity.