Two Pointers: Explaination and code in Python, Java, C++, and JavaScript

Two Pointers: A Hands-On Guide with Examples

The Two Pointers technique is a practical tool that can simplify and speed up problem-solving in programming. Let’s jump straight into some hands-on examples to see how it works.

Example 1: Finding a Pair with a Specific Sum

Problem: Given a sorted array, find two numbers that add up to a target sum.

Array: [1, 3, 4, 6, 8, 10] Target Sum: 10

Steps:

1. Place the first pointer (left) at the start (index 0) and the second pointer (right) at the end (index 5) of the array.
2. Check the sum of the elements at these pointers: 1 + 10 = 11.
3. Since 11 > 10, move the right pointer one step left to index 4.
4. Now, check 1 + 8 = 9.
5. Since 9 < 10, move the left pointer one step right to index 1.
6. Now, check 3 + 8 = 11. Again too high, so move right left to index 3.
7. Finally, check 3 + 6 = 9. Still low, so move left right to index 2.
8. Check 4 + 6 = 10. Perfect match!

Result: The pair is (4, 6).

Example 2: Reversing a String

Problem: Reverse a string in place.

String: "hello"

Steps:

1. Place one pointer (left) at the start (index 0) and the other (right) at the end (index 4).
2. Swap the characters at these pointers: "o" and "h".
3. Move left right to index 1 and right left to index 3.
4. Swap again: "e" and "l".
5. Move the pointers inward: left to index 2 and right to index 2.
6. Now both pointers meet in the middle, so the string is reversed.

Result: The reversed string is "olleh".

Example 3: Merging Two Sorted Arrays

Problem: Merge two sorted arrays into a single sorted array.

Arrays: [1, 4, 6] and [2, 3, 5]

Steps:

1. Place i at the start of the first array and j at the start of the second array.
2. Compare 1 (from the first array) and 2 (from the second array). Add 1 to the result and move i to the next position.
3. Compare 4 and 2. Add 2 and move j right.
4. Compare 4 and 3. Add 3 and move j right.
5. Compare 4 and 5. Add 4 and move i right.
6. Continue this process until all elements are added.

Result: The merged array is [1, 2, 3, 4, 5, 6].

Here’s how you can implement the Two Pointers technique in Python, Java, C++, and JavaScript for each of the examples provided.

Example 1: Finding a Pair with a Specific Sum

Python

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

# Usage
arr = [1, 3, 4, 6, 8, 10]
target = 10
print(find_pair(arr, target))  # Output: (4, 6)

Java

public class TwoPointersExample {
    public static int[] findPair(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left < right) {
            int currentSum = arr[left] + arr[right];
            if (currentSum == target) {
                return new int[]{arr[left], arr[right]};
            } else if (currentSum < target) {
                left++;
            } else {
                right--;
            }
        }
        return null;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 4, 6, 8, 10};
        int target = 10;
        int[] result = findPair(arr, target);
        if (result != null) {
            System.out.println(result[0] + ", " + result[1]);  // Output: 4, 6
        }
    }
}

C++

#include <iostream>
#include <vector>

std::pair<int, int> findPair(const std::vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left < right) {
        int currentSum = arr[left] + arr[right];
        if (currentSum == target) {
            return {arr[left], arr[right]};
        } else if (currentSum < target) {
            left++;
        } else {
            right--;
        }
    }
    return {-1, -1};  // Indicates no pair found
}

int main() {
    std::vector<int> arr = {1, 3, 4, 6, 8, 10};
    int target = 10;
    auto result = findPair(arr, target);
    if (result.first != -1) {
        std::cout << result.first << ", " << result.second << std::endl;  // Output: 4, 6
    }
    return 0;
}

JavaScript

function findPair(arr, target) {
    let left = 0, right = arr.length - 1;
    while (left < right) {
        const currentSum = arr[left] + arr[right];
        if (currentSum === target) {
            return [arr[left], arr[right]];
        } else if (currentSum < target) {
            left++;
        } else {
            right--;
        }
    }
    return null;
}

// Usage
const arr = [1, 3, 4, 6, 8, 10];
const target = 10;
console.log(findPair(arr, target));  // Output: [4, 6]

Example 2: Reversing a String

Python

def reverse_string(s):
    left, right = 0, len(s) - 1
    s = list(s)
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1
    return ''.join(s)

# Usage
s = "hello"
print(reverse_string(s))  # Output: "olleh"

Java

public class ReverseString {
    public static String reverseString(String s) {
        char[] chars = s.toCharArray();
        int left = 0, right = chars.length - 1;
        while (left < right) {
            char temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
        return new String(chars);
    }

    public static void main(String[] args) {
        String s = "hello";
        System.out.println(reverseString(s));  // Output: "olleh"
    }
}

C++

#include <iostream>
#include <string>

std::string reverseString(const std::string& s) {
    std::string reversed = s;
    int left = 0, right = reversed.size() - 1;
    while (left < right) {
        std::swap(reversed[left], reversed[right]);
        left++;
        right--;
    }
    return reversed;
}

int main() {
    std::string s = "hello";
    std::cout << reverseString(s) << std::endl;  // Output: "olleh"
    return 0;
}

JavaScript

function reverseString(s) {
    let left = 0, right = s.length - 1;
    const chars = s.split('');
    while (left < right) {
        [chars[left], chars[right]] = [chars[right], chars[left]];
        left++;
        right--;
    }
    return chars.join('');
}

// Usage
const s = "hello";
console.log(reverseString(s));  // Output: "olleh"

Example 3: Merging Two Sorted Arrays

Python

def merge_sorted_arrays(arr1, arr2):
    merged = []
    i, j = 0, 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            merged.append(arr1[i])
            i += 1
        else:
            merged.append(arr2[j])
            j += 1
    # Append remaining elements
    merged.extend(arr1[i:])
    merged.extend(arr2[j:])
    return merged

# Usage
arr1 = [1, 4, 6]
arr2 = [2, 3, 5]
print(merge_sorted_arrays(arr1, arr2))  # Output: [1, 2, 3, 4, 5, 6]

Java

import java.util.ArrayList;
import java.util.Arrays;

public class MergeSortedArrays {
    public static int[] mergeSortedArrays(int[] arr1, int[] arr2) {
        int[] merged = new int[arr1.length + arr2.length];
        int i = 0, j = 0, k = 0;
        while (i < arr1.length && j < arr2.length) {
            if (arr1[i] < arr2[j]) {
                merged[k++] = arr1[i++];
            } else {
                merged[k++] = arr2[j++];
            }
        }
        while (i < arr1.length) {
            merged[k++] = arr1[i++];
        }
        while (j < arr2.length) {
            merged[k++] = arr2[j++];
        }
        return merged;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 4, 6};
        int[] arr2 = {2, 3, 5};
        System.out.println(Arrays.toString(mergeSortedArrays(arr1, arr2)));  // Output: [1, 2, 3, 4, 5, 6]
    }
}

C++

#include <iostream>
#include <vector>

std::vector<int> mergeSortedArrays(const std::vector<int>& arr1, const std::vector<int>& arr2) {
    std::vector<int> merged;
    int i = 0, j = 0;
    while (i < arr1.size() && j < arr2.size()) {
        if (arr1[i] < arr2[j]) {
            merged.push_back(arr1[i++]);
        } else {
            merged.push_back(arr2[j++]);
        }
    }
    while (i < arr1.size()) {
        merged.push_back(arr1[i++]);
    }
    while (j < arr2.size()) {
        merged.push_back(arr2[j++]);
    }
    return merged;
}

int main() {
    std::vector<int> arr1 = {1, 4, 6};
    std::vector<int> arr2 = {2, 3, 5};
    std::vector<int> result = mergeSortedArrays(arr1, arr2);
    for (int num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;  // Output: 1 2 3 4 5 6
    return 0;
}

JavaScript

function mergeSortedArrays(arr1, arr2) {
    const merged = [];
    let i = 0, j = 0;
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            merged.push(arr1[i++]);
        } else {
            merged.push(arr2[j++]);
        }
    }
    while (i < arr1.length) {
        merged.push(arr1[i++]);
    }
    while (j < arr2.length) {
        merged.push(arr2[j++]);
    }
    return merged;
}

// Usage
const arr1 = [1, 4, 6];
const arr2 = [2, 3, 5];
console.log(mergeSortedArrays(arr1, arr2));  // Output: [1, 2, 3, 4, 5, 6]

Conclusion

Two Pointers can make your coding life easier by offering a clear and efficient way to solve problems. Whether you’re finding pairs, reversing strings, or merging arrays, try using Two Pointers in your next coding challenge!