Two Pointers Technique in Algorithms

Proceed only if you are here because:

• You have started learning coding patterns.
• You possess a fundamental knowledge of a programming language.
• You believe in consistency and are committed to problem-solving.
• You remember to practice pseudocoding while tackling problems by:
  — Reading the problem statement thoroughly.
  — Writing and comprehending the coding technique.
  — Identifying the data types involved.
  — Determining the expected output data types.
  — Writing the initial solution.
  — Optimizing the solution.
  — Testing the solution against different test cases.

Now getting back to the concept —

One of the most versatile and efficient methods used to solve a wide range of problems is the “Two Pointers Technique.” This approach involves using two pointers to traverse the data structure, which can often simplify and optimize the solution.

What is the Two Pointers Technique?

The Two Pointers Technique uses two indices to traverse an array or list. Depending on the problem, the pointers can move towards each other, away from each other, or in the same direction. This method is particularly effective for problems involving searching, sorting, and partitioning.

Applications of the Two Pointers Technique

1. Finding Pair Sums: Identifying two elements in an array that sum up to a target value.
2. Removing Duplicates: Eliminating duplicate values in a sorted array.
3. Reversing Parts of an Array: Reversing a segment of an array.
4. Merging Two Sorted Arrays: Combining two sorted arrays into a single sorted array.
5. Detecting Cycles in Linked Lists: Identifying cycles in linked lists using fast and slow pointers.

Example Problems and Walkthroughs — Variations of Two Pointers Technique

1. Starting from Both Ends of the Array

Two Sum II — Input Array Is Sorted

Given a sorted array of integers, find two numbers such that they add up to a specific target.

Two Pointers Approach: Use two pointers, one starting at the beginning (`left`) and one at the end (`right`). Move them towards each other based on the sum comparison.

1. Initialize `left` at the start and `right` at the end of the array.
2. Calculate the sum of the elements at the `left` and `right` pointers.
3. If the sum equals the target, return the indices.
4. If the sum is less than the target, move the `left` pointer to the right.
5. If the sum is greater than the target, move the `right` pointer to the left.
6. Repeat until the pointers meet or the target is found.

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

numbers = [2, 7, 11, 15]
target = 9
print(two_sum_sorted(numbers, target))  # Output: [0, 1]

2. Slow and Fast Pointer

Move Zeroes

Given an array of integers, move all zeroes to the end while maintaining the relative order of the non-zero elements.

Two Pointers Approach: Use a slow pointer to track the position of the next non-zero element and a fast pointer to explore the array.

1. Initialize `slow` at the start of the array.
2. Iterate through the array with `fast` pointer.
3. If the element at `fast` is not zero, swap it with the element at `slow` and increment `slow`.
4. Continue until all elements have been processed.

def move_zeroes(nums):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow], nums[fast] = nums[fast], nums[slow]
            slow += 1

nums = [0, 1, 0, 3, 12]
move_zeroes(nums)
print(nums)  # Output: [1, 3, 12, 0, 0]

3. Split Array and Start a Pointer from Each Split

Minimum Size Subarray Sum

Given an array of positive integers and a positive integer target, return the minimal length of a contiguous subarray of which the sum is greater than or equal to the target.

Two Pointers Approach: Use a sliding window with two pointers starting at the beginning of the array.

1. Initialize `left` at the start and `current_sum` to 0.
2. Iterate through the array with `right` pointer.
3. Add the element at `right` to `current_sum`.
4. While `current_sum` is greater than or equal to `target`, update `min_len` and subtract the element at `left` from `current_sum`, then increment `left`.
5. Continue until the end of the array and return the minimum length found.

def min_subarray_len(target, nums):
    left = 0
    current_sum = 0
    min_len = float('inf')
    
    for right in range(len(nums)):
        current_sum += nums[right]
        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= nums[left]
            left += 1
    
    return min_len if min_len != float('inf') else 0

nums = [2, 3, 1, 2, 4, 3]
target = 7
print(min_subarray_len(target, nums))  # Output: 2 (subarray: [4, 3])

Why Use the Two Pointers Technique?

1. Efficiency: Often reduces the time complexity from O(n²) to O(n) for many problems.
2. Simplicity: The logic is straightforward and easy to implement.
3. Versatility: Applicable to a wide range of problems involving arrays and linked lists.

When to Avoid the Two Pointers Technique?

1. Unsorted Data: If the problem requires operations on unsorted data where order matters.
2. Non-Linear Structures: For data structures like trees or graphs, two pointers might not be applicable.
3. Overlapping Scenarios: In cases where the problem requires overlapping subarrays or subsequences, the technique might not be optimal.

POV —

Stay consistent, practice regularly, and you’ll see improvement in your problem-solving skills. Remember, the key to mastering coding patterns is practice and understanding. Keep coding!

Had fun? For more coding pattern concepts, follow the link — https://medium.com/@shraddharao_/follow-this-trick-to-learn-data-structures-algorithms-5dc3ded0933f