# The Two-Pointers Technique

### Sergei Golitsyn provides solutions to popular problems experienced using the two-pointers technique: Valid Palindrome, Two Sum II — Input Array Is Sorted, and 3Sum.

Join the DZone community and get the full member experience.

Join For FreeAloha, guys. Today, we will address more frequently asked questions and solve a few problems using the two-pointers technique.

This approach is widely used in interview tasks. It is crucial to read the patterns in the condition of the problem and use them when solving it. This approach aims to create two-pointers, usually fast and slow pointers. After that, depending on the condition of the problem, we will move the fast/slow pointers.

This approach will be more evident with an example. Our first task:

## Valid Palindrome

**Description**

A phrase is a **palindrome** if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.

Given a string `s`

, return `true`

* if it is a palindrome, or *

`false`

*otherwise*.

**Example 1:**

```
Input: s = "A man, a plan, a canal: Panama"
Output: true
Explanation: "amanaplanacanalpanama" is a palindrome.
```

**Example 2:**

```
Input: s = "race a car"
Output: false
Explanation: "raceacar" is not a palindrome.
```

**Example 3:**

```
Input: s = " "
Output: true
Explanation: s is an empty string "" after removing non-alphanumeric characters.
Since an empty string reads the same forward and backward, it is a palindrome.
```

### Solution

Let's start with a simple example, `aba`

. Based on the description, we should check the start and end. And if they are the same, we should check the next pair. Is it clear?

And to do it, we can add two pointers, start and end. For moving to another pair, we can increase the start pointer and decrease the end pointer `(start++, end--)`

.

But in our String, we can have some specific characters like `:`

or `*`

. How can we handle it? We can skip this character and move forward or back. For better understanding, if the current char on the start pointer is not a letter or digit, we should increase it (or decrease it for the end pointer).

Let's dive deep into the code section:

### Code

```
public boolean isPalindrome(String s) {
if (s == null || s.isEmpty()) {
return false;
}
if (s.length() == 1) {
return true;
}
int start = 0;
int end = s.length() - 1;
s = s.toLowerCase();
while (start < end) {
char a = s.charAt(start);
char b = s.charAt(end);
if (!Character.isLetterOrDigit(a)) {
start++;
continue;
}
if (!Character.isLetterOrDigit(b)) {
end--;
continue;
}
if (a != b) {
return false;
}
start++;
end--;
}
return true;
}
```

Our next problem is:

## Two Sum II — Input Array Is Sorted

**Description**

Given a **1-indexed** array of integers `numbers`

that is already ** sorted in non-decreasing order**, find two numbers such that they add up to a specific

`target`

number. Let these two numbers be `numbers[index`_{1}]

and `numbers[index`_{2}]

where `1 <= index`_{1} < index_{2} <= numbers.length

.Return* the indices of the two numbers, *`index`

_{1}* and *`index`

_{2}*, added by one as an integer array *

`[index`_{1}, index_{2}]

*of length 2.*

The tests are generated such that there is **exactly one solution**. You **may not** use the same element twice.

Your solution must use only constant extra space.

**Example 1:**

```
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
```

**Example 2:**

```
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].
```

**Example 3:**

```
Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].
```

### Solution

We know that our numbers array is sorted. But what is it mean? It means that `numbers[0]`

< `numbers[1]`

and so on. Can we use it? Sure, we can prepare two pointers, start and end. Then we can check the sum of the elements on these pointers. Like `numbers[start]`

+ `numbers[end]`

. After it, we should analyze this sum. If we have a sum lover than the target, we should increase it. And if our sum is bigger than the target, we should reduce it. That is obvious, right? For increasing the sum, we should move forward the start pointer and decrease the end pointer to reduce the sum.

### Code

```
public int[] twoSum(int[] numbers, int target) {
int[] rez = new int[2];
int start = 0;
int end = numbers.length - 1;
while (start < end) {
int a = numbers[start];
int b = numbers[end];
if (a + b == target) {
rez[0] = start + 1;
rez[1] = end + 1;
return rez;
} else if (a + b > target) {
end--;
} else {
start++;
}
}
return rez;
}
```

Congratulations. Now you know how to find a sum in a sorted array.

And our last problem for today is:

**3Sum**

**Description**

Given an integer array nums, return all the triplets `[nums[i], nums[j], nums[k]]`

such that `i != j`

, `i != k`

, and `j != k`

, and `nums[i] + nums[j] + nums[k] == 0`

.

Notice that the solution set must not contain duplicate triplets.

**Example 1:**

```
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
```

**Example 2:**

```
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
```

**Example 3:**

```
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
```

### Solution

That is a popular interview problem. And I'm going to show you a solution with two pointers.

The main idea of this algorithm is to check all available triplets and, depending on the result, increase or decrease the sum.

First of all, we need to sort the array. Then I want to iterate over the array and get element one on index i.

Then we can prepare two elements. So, the second (start pointer) element will be on position *i + 1,* and the third (end pointer) will be on position *length - 1. *Then based on the sum, we can move start/end pointers.

### Code

```
public List<List<Integer>> threeSum(int[] nums) {
if (nums.length < 3) {
return new ArrayList<>();
}
Arrays.sort(nums);
List<List<Integer>> rez = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int start = i + 1;
int end = nums.length - 1;
while (start < end) {
int threeSum = nums[i] + nums[start] + nums[end];
if (threeSum == 0) {
List<Integer> tmp = List.of(nums[i], nums[start], nums[end]);
rez.add(tmp);
// todo add while iteration
while (start < end && nums[start] == nums[start + 1]) {
start++;
}
while (end > start && nums[end - 1] == nums[end]) {
end--;
}
start++;
end--;
} else if (threeSum > 0) {
end--;
} else {
start++;
}
}
}
return rez;
}
```

Also, we can try to solve this problem with the hashing approach. But that is a topic for another article.

Opinions expressed by DZone contributors are their own.

Comments