Introduction

Today we will be learning about the Two Pointer pattern to solve the problems. I will go through an overview, its understanding, its variations, and teach you how to recognize when to use this technique.

Overview

First thing we need to know is the pointer So, what is a pointer?

A pointer is an object that stores the memory address of another object or we can say that a pointer references another object. An easy way to remember is a pointer points at another object. For our unit, pointer is an an integer that indicates an index in an array or string.

Let's break down the concept of pointers with a simple analogy. Imagine you have a treasure map that leads to a buried treasure. The map itself doesn't contain the treasure, but it points you to its location. Similarly, a pointer doesn't hold the actual data but points you to where it's stored in memory.

Understanding the Two Pointers Pattern

The Two Pointers pattern is based on using two pointers to traverse a data structure (mostly array || string) simultaneously. Most of the time these pointers are known as the left pointer and right pointer. These pointers point to different locations in the data structure (array || string).

These pointers can move in the same direction or in opposite directions depending on the problem requirements.

• This technique is particularly useful for solving problems involving arrays or linked lists efficiently.
• This technique reduce the time complexity of solutions from O(N^2) to O(N) || O(N log N).

Basic Idea

• Initialization: Initialize two pointers, usually named left and right, pointing to the start and end of the array or linked list.
• Traverse the Data Structure: Move the pointers based on certain conditions until the solution is found.

Example: Two Sum Problem

Consider: Given an sorted array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Example:

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]

Let's first find out the brute force solution for it:

Brute Force Approach:

The brute force solution involves using nested loops to check every pair of elements in the array and see if their sum equals the target.

#include <vector>

std::vector<int> twoSumBruteForce(std::vector<int>& nums, int target) {
    std::vector<int> result;
    for (int i = 0; i < nums.size(); ++i) {
        for (int j = i + 1; j < nums.size(); ++j) {
            if (nums[i] + nums[j] == target) {
                result.push_back(i);
                result.push_back(j);
                return result;
            }
        }
    }
    return result;
}

• Time Complexity: O(n^2), where n is the number of elements in the array.
  • We use two nested loops to check every pair of elements in the array, resulting in a quadratic time complexity.
• Space Complexity: O(1)
  • We use a constant amount of extra space.

Two Pointers Approach:

The two pointers solution takes advantage of the fact that the input array is sorted. We use two pointers, left and right, initialized at the beginning and end of the array, respectively. We move the pointers towards each other until we find the pair that sums up to the target.

#include <vector>
#include <algorithm>

std::vector<int> twoSumTwoPointers(std::vector<int>& nums, int target) {
    std::vector<int> result;
    int left = 0, right = nums.size() - 1;
    
    while (left < right) {
        int sum = nums[left] + nums[right];
        if (sum == target) {
            result.push_back(left);
            result.push_back(right);
            return result;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
    return result;
}

• Time Complexity: O(n), where n is the number of elements in the array.
  • We use two pointers (left and right) that traverse the array once, resulting in a linear time complexity.
• Space Complexity: O(1)
  • We use a constant amount of extra space for the result vector.

Variations of Two Pointers

1 Opposite-Directional:

In this, one pointer starts from the beginning while the other pointer starts from the end. They move towards each other until both meet or some condition satisfy.

2 Equi-Directional:

Both start from the beginning. One slow-runner and the other fast-runner. For e.g., Sliding Window or In Linked List to find intersection and loop.

When Do We Use It

In many problems involving collections such as arrays or lists, we have to analyze each element of the collection compared to its other elements.

There are many approaches to solving problems like these. For example we usually start from the first index and iterate through the data structure one or more times depending on how we implement our code.

Sometimes we may even have to create an additional data structure depending on the problem's requirements. This approach might give us the correct result, but it likely won't give us the most space and time efficient result.

This is why the two-pointer technique is efficient. We are able to process two elements per loop instead of just one. Common patterns in the two-pointer approach entail:

1. Two pointers, each starting from the beginning and the end until they both meet.
2. One pointer moving at a slow pace, while the other pointer moves at twice the speed.

These patterns can be used for string or array questions. They can also be streamlined and made more efficient by iterating through two parts of an object simultaneously.

The Two Pointers technique is particularly useful when dealing with problems involving arrays or linked lists, especially when:

1. The Array is Sorted:
   1. When the array is sorted, the Two Pointers technique can be very effective. However, we can use it for unsorted array as well as it require additional steps, like sorting the array.
   2. Examples: Finding pairs with a target sum, finding triplets with a target sum, finding the longest subarray with a given sum.
2. Sliding Window Problems:
   1. When dealing with problems involving a contiguous subarray of a given size, such as finding the maximum sum of a subarray of size K.
   2. Examples: Maximum sum subarray of size K, smallest subarray with a given sum.
3. Intersection or Union of Two Arrays:
   1. When dealing with problems involving two arrays, and you need to find common elements, or merge the arrays.
   2. Examples: Intersection of two arrays, merging two sorted arrays.
4. Linked Lists:
   1. When dealing with problems involving linked lists and you need to find a specific pattern or do some operations.
   2. Examples: Detecting cycles in a linked list, finding the intersection point of two linked lists.
5. Search Problems:
   1. When dealing with search problems and you need to find elements that meet certain criteria.
   2. Examples: Binary search, finding the closest sum to a target value.

When to Use It:

1. Use the Two Pointers technique when you need to efficiently solve problems involving arrays or linked lists.
2. Use it when the array is sorted, or when you need to maintain two pointers to traverse the array or list simultaneously.
3. Use it when you need to reduce the time complexity of your solution from O(N^2) to O(N) or better.

When Not to Use It:

1. Avoid using the Two Pointers technique when the array is not sorted, and the problem doesn't require two pointers to traverse the array.
2. If the problem doesn't involve arrays or linked lists, using the Two Pointers technique may not be appropriate.

Key Advantages

1. Reduced Time Complexity: Using the Two Pointers pattern, we can often solve problems in linear time O(N), which would otherwise require a quadratic time O(N^2) solution.
2. No Extra Space: The Two Pointers technique typically operates in constant space O(1), making it memory efficient.