Two Pointers in Java: 5 Must-Know Patterns | DSA

Here's a question. You have a sorted list of one million numbers. Find two numbers that add up to a target.

If you check every possible pair, that's about half a trillion checks. Your program would run for hours.

But with one simple trick, you need at most one million steps. In under a second.

That trick is called two pointers. And by the end of this video, you'll know five patterns that use it.

Welcome back to Compiled Canvas. This is Episode Nine of our DSA series. Last time, we learned the prefix sum. Today, we learn the trick we used when we reversed an array. And it solves a whole family of problems.

Here's the plan. What two pointers are. Pattern one, reverse. Pattern two, palindrome. Pattern three, pair sum. Pattern four, remove duplicates. Pattern five, move zeroes. Real Java code. The one mistake everyone makes. A cheat sheet. And an easy quiz at the end.

Let's go.

First, what are two pointers?

A pointer is just an index. A number that says which box you're looking at. Two pointers means we look at two boxes at the same time, and move them in a smart way.

There are two kinds. In the first kind, the pointers start at both ends, and walk towards each other. In the second kind, both pointers start at the left, and walk in the same direction. One goes fast, one goes slow.

Think of two friends cleaning a long bookshelf. One starts at the left end, one starts at the right end. They walk towards each other, and when they meet in the middle, the job is done. Nobody walks the whole shelf.

Pattern one. Reverse an array.

Take one, two, three, four, five. Left points at the first box. Right points at the last box.

Swap them. Now it's five, two, three, four, one. Move left forward, and move right back.

Swap again. Two and four change places. Five, four, three, two, one.

Now both pointers are at the middle box. They've met, so we stop. Two swaps, and the array is reversed.

Pattern two. Is a word a palindrome? A palindrome reads the same from both ends. Like madam.

Left points at the first letter, right points at the last. M and M. Same. Move both in. A and A. Same. Now both pointers meet at D. So madam is a palindrome.

Now try mango. M and O. Different. We stop right there. Mango is not a palindrome. One check was enough.

Pattern three. Pair sum. This is the big one.

Imagine you're in a shop with exactly eighty-five rupees. You want to buy two items, and spend all of it. The prices are sorted: ten, twenty-five, thirty-five, fifty, sixty, eighty-five.

Left points at the cheapest item, ten. Right points at the costliest, eighty-five.

Ten plus eighty-five is ninety-five. Too much. The total is too big, so we need a smaller number. Move right back, to sixty.

Ten plus sixty is seventy. Too little. Now we need a bigger number. Move left forward, to twenty-five.

Twenty-five plus sixty is eighty-five. Exactly our budget. Found it!

So the rule is simple. If the sum is too big, move right back. If the sum is too small, move left forward. If it's equal, you're done.

Why does it work? Because the list is sorted. Moving left forward always makes the sum bigger. Moving right back always makes the sum smaller. So every step throws away one number we never need again.

Your turn. Pause the video and try this one. The sorted list is two, four, five, seven, nine. Find two numbers that add up to twelve.

Ready? Two plus nine is eleven. Too small, move left. Four plus nine is thirteen. Too big, move right. Four plus seven is eleven. Too small, move left. Five plus seven is twelve. Found it! If you got five and seven, you've got it.

Look at this graph. Along the bottom is the size of the list. Up the side is the number of steps. Checking every pair is a curve that shoots up, because it's n times n. Two pointers is a straight, low line. Each step moves one pointer, so it's just n steps.

Quick pause, before we go further. If you're finding this video valuable, hit subscribe to Compiled Canvas, and turn on the bell. It's free, it takes one second, and it helps me keep making this complete DSA series for you. Alright, back to it.

Now the second kind. Both pointers start at the left. We call them slow and fast.

Think of packing a bag. One hand picks up every item, one by one. That's fast. The other hand only puts the good items into the bag. That's slow.

Pattern four. Remove duplicates from a sorted array.

Take one, one, two, two, three. Slow stays at the first box, and keeps the first one.

Fast moves to the next box. It's one again. Same as what slow has, so we skip it.

Fast moves on, and finds two. That's new! Slow moves forward one box, and writes two there.

Fast finds two again. Same, so we skip it.

Fast finds three. New again! Slow moves forward, and writes three.

Now the first three boxes are one, two, three. Three unique numbers, in one pass.

Pattern five. Move all the zeroes to the end.

Take zero, one, zero, three, twelve. Slow waits at the first box. Fast walks every box.

Fast sees zero. Skip it.

Fast sees one. Not a zero! Swap it with the box at slow. Now it's one, zero, zero, three, twelve. Slow moves forward.

Fast sees zero. Skip it.

Fast sees three. Swap it with the box at slow. One, three, zero, zero, twelve. Slow moves forward.

Fast sees twelve. Swap again. One, three, twelve, zero, zero. All the zeroes are at the end, and the other numbers kept their order.

Now let's write it in Java.

Here's pair sum. Left starts at zero. Right starts at the last index.

While left is less than right, we add the two numbers.

If the sum equals the target, we found our pair.

If the sum is too small, left plus plus. If it's too big, right minus minus.

And here's move zeroes. Slow starts at zero. Fast walks every box in a for loop. If the number at fast is not zero, swap it with the number at slow, and move slow forward.

Both of them visit every box at most once. So the time is O of n. And they only use two extra variables, so the extra space is O of one.

Now, the one mistake everyone makes.

Pair sum with two pointers only works on a sorted list. If the list is not sorted, moving left forward might make the sum smaller, and you'll walk right past the answer.

So if the list isn't sorted, sort it first. Or use a hash map, which we'll learn later in this series.

One more small tip. Use left less than right, not less than or equal. Otherwise both pointers can land on the same box, and you'll use one number twice.

So, here's the whole two pointers trick in one cheat sheet. Pause and screenshot this.

A pointer is just an index. Two pointers move in a smart way.

From both ends: reverse, palindrome, and pair sum.

Same direction, slow and fast: remove duplicates, and move zeroes.

Pair sum: too big, move right back. Too small, move left forward.

Time: O of n. Extra space: O of one.

And pair sum needs a sorted list.

Okay, quiz time. Three easy questions. Pause the video, think, and then hit play.

Question one. Is the word noon a palindrome?

Question two. The sorted list is one, two, four, seven, eleven. Which two numbers add up to nine?

Question three. What is the time, and the extra space, of two pointers?

Ready?

Question one: yes. N and N are the same. O and O are the same. Then the pointers cross, so noon is a palindrome.

Question two: two and seven. One plus eleven is twelve, too big, so right moves back. One plus seven is eight, too small, so left moves forward. Two plus seven is nine.

Question three: time is O of n, and extra space is O of one.

How many did you get right? Tell me in the comments: three out of three, two, or one.

Let's recap. A pointer is just an index, and two pointers look at two boxes at once. From both ends: reverse, palindrome, and pair sum. Same direction, slow and fast: remove duplicates, and move zeroes. In pair sum, too big means move right back, and too small means move left forward. It needs a sorted list. Time is O of n, and extra space is O of one.

Your homework. Solve Two Sum Two on LeetCode. It's the exact pair sum from this video. Then try Move Zeroes, and Valid Palindrome. All of them, with hints and full Java answers, are on our free practice page. The link is in the description. And tell me in the comments: in the sorted list one, two, three, four, six, which two numbers add up to six?

Next episode, we learn the sliding window. It's like two pointers, but the two pointers carry a whole window between them, and it makes problems like the biggest sum of k numbers in a row super fast.

And don't forget to subscribe to Compiled Canvas, so you don't miss anything new in tech and the job market. Keep coding, stay consistent, and I'll see you in the next one.