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 



<p>Picture the numbers as cute little characters in a line:<br>
① ② ③ ④ ⑤</p>

<p><img src="/static/imghwm/default1.png" data-src="https://img.php.cn/upload/article/000/000/000/173624608458262.jpg?x-oss-process=image/resize,p_40" class="lazy" alt="Two pointer pattern in DSA"></p>

• 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 



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

<p>Palindrome confirmed! ?</p>

<p>Some cool applications of this technique:</p>

<ol>
<li>Finding a target sum (like we did above)</li>
<li>Merging two sorted arrays</li>
<li>Calculating trapped rainwater (Google this one, it's fascinating!)</li>
<li>Reversing linked lists</li>
</ol>

<p>Pro tips:</p>

• 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!