Two Pointer Pattern

November 17, 2024

The two-pointer technique is a powerful approach used to optimize algorithms involving arrays, strings, or linked lists. Instead of using nested loops (which can be slow), we use two variables ("pointers") that traverse the data in a structured way.

Types of Two-Pointer Approaches

1. Opposite Direction (Two Ends)

Used for: Searching, sorting, pair sum, palindrome checking, etc.
Idea: One pointer starts at the beginning, and the other at the end. They move toward each other.

2. Same Direction (Sliding Window)

Used for: Finding subarrays, longest substring problems, etc.
Idea: Both pointers move in the same direction to maintain a range.

3. Fast and Slow Pointer (Tortoise and Hare)

Used for: Detecting cycles in linked lists, finding middle elements, etc.
Idea: One pointer moves slowly (one step at a time), while the other moves faster (two steps at a time).

1. Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6 Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6 Output: [0,1]

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Intuition

The problem is to find two numbers in the array that add up to a given target. A straightforward way would be to use two loops and check every combination of two numbers. However, this would be inefficient.

Sorting the array increases time complexity.

A more efficient way would be to use a hashmap (or in JavaScript, a Map) to store the numbers we've seen so far and their indices. As we iterate through the array, for each number, we can check if the difference between the target and that number exists in the map. If it does, we've found our two numbers.

Approach for unsorted array using hashmap

Using HashMap and Javascript Object

Initialize an empty Map.
Iterate through the array.
For each number, calculate the difference between the target and that number.
Check if this difference exists in the Map.
If it does, return the index of the difference from the Map and the current index.
If not, add the current number and its index to the Map.

Complexity

Time complexity:

The time complexity is (O(n)) because we iterate through the array once, and operations with the Map (both get and set) are on average (O(1)).

Space complexity:

The space complexity is (O(n)) because in the worst case, we might store all numbers in the Map.

Code

HashMap

function twoSum(nums: number[], target: number): number[] {
    const numToIndex = new Map()
    for(let i:number =0; i<nums.length; i++) {
        const complement = target - nums[i]
        if(numToIndex.has(complement)) return [numToIndex.get(complement), i];
        numToIndex.set(nums[i], i);
    }
};

Map is more memory-intensive because of its advanced functionality and robust key handling.
The implementation uses a single pass through the array, storing each number's index in a Map.
Time complexity: O(n) - We traverse the list containing n elements only once.
Space complexity: O(n) - The extra space required depends on the number of items stored in the hash map, which stores at most n elements.

Approach using Two pointer

function twoSumSorted(nums, target) {
    let left = 0, right = nums.length - 1;
 
    while (left < right) {
        let sum = nums[left] + nums[right];
 
        if (sum === target) return [left, right];  // Found the pair
        else if (sum < target) left++;   // Move left pointer
        else right--;  // Move right pointer
    }
 
    return [];  // No solution (should not happen as per the problem)
}