Two pointer pattern in DSA

Hey there! Let's chat about this cool trick called the two-pointer technique in DSA. Don't worry, I'll keep it fun and throw in some visuals to help it stick. Ready to dive in?

So, what's this two-pointer thing all about?

Think of it like a game where you've got two players (we'll call them pointers) starting on different sides of a field (that's your array). They can either:

1. Run towards each other (kinda romantic, right?)
2. Race in the same direction (getting competitive!)
3. Do their own thing (freestyle mode)

This technique helps you solve a bunch of problems super efficiently without writing a ton of loops. Pretty neat, huh?

Why should you care about it?

Well, it's like a superpower for your code:

• It's fast: Solves problems in O(n) instead of O(n²). Your code will zoom!
• It's simple: Fewer lines, easier to understand.
• It's flexible: Works with arrays, strings, even linked lists!

Let's look at some types of two-pointer problems

1. Pointers Moving Toward Each Other

Imagine you're trying to find two numbers in a sorted array that add up to a target. It's like two people running towards each other to meet in the middle.

Here's a quick JavaScript example:

function twoSumSorted(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    while (left < right) {
        const sum = arr[left] + arr[right];
        if (sum === target) return [left, right];
        if (sum < target) left++;
        else right--;
    }
    return -1; // No pair found
}

console.log(twoSumSorted([1, 2, 3, 4, 6], 10)); // Output: [2, 4]

Picture the numbers as cute little characters in a line:
① ② ③ ④ ⑤

• Left pointer starts at ①
• Right pointer starts at ⑤
• They slowly move towards each other to find the perfect match

2.This is perfect for checking if a string is a palindrome. Picture two friends starting at the ends of a word, moving towards the middle and high-fiving if everything matches.

function isPalindrome(s) {
    let left = 0;
    let right = s.length - 1;

    while (left < right) {
        if (s[left] !== s[right]) return false;
        left++;
        right--;
    }

    return true;
}

console.log(isPalindrome("racecar")); // Output: true
console.log(isPalindrome("hello"));   // Output: false

Imagine two ants crawling towards each other on the word "racecar":
r <-> r ?
a <-> a ?
c <-> c ?

Palindrome confirmed! ?

Some cool applications of this technique:

1. Finding a target sum (like we did above)
2. Merging two sorted arrays
3. Calculating trapped rainwater (Google this one, it's fascinating!)
4. Reversing linked lists

Pro tips:

• Sorting first can make these problems way easier
• Watch out for edge cases (empty arrays, duplicates, extreme values)
• Sketch it out! Drawing the array or string can help you avoid bugs

Want to level up? Try these challenges:

1. Two Sum II - Input Array Is Sorted (LeetCode 167)
2. Longest Substring Without Repeating Characters (LeetCode 3)
3. Valid Palindrome (LeetCode 125)
4. Trapping Rain Water (LeetCode 42) - if you're feeling adventurous!

The two-pointer technique is like a Swiss Army knife for coding. It's simple but powerful, and with some practice, you'll be using it without even thinking.

Got questions or want to share your solutions? Drop a comment or give me a shout. Happy coding!

The above is the detailed content of Two pointer pattern in DSA. For more information, please follow other related articles on the PHP Chinese website!