One of the techniques of iterating through an array is the *two pointers technique*, and it is as simple as it sounds: we just keep two pointers, one starting from the left, and the other from the right, gradually getting closer to each other.

### Palindrome example

A very basic example can be the one where we check if a string is a palindrome or not. A palindrome is a string that reads the same forwards and backwards.

In an imaginary world where all the inputs always consist of lowercase English letters, we can do it like this:

```
// s consists of lowercase English letters
function isPalindrome(s: string) {
let left = 0;
let right = s.length - 1;
while (left <= right) {
if (s[left++] !== s[right--]) {
return false;
}
}
return true;
}
```

We initialize two pointers: `left`

and `right`

. `left`

points to the start of the array, while the `right`

points to the last element. As we loop while `left`

is less than `right`

, we check if they are equal. If not, we return `false`

immediately. Otherwise, our `left`

pointer is increased; that is, it's moved to the *right* one step, and our `right`

pointer is decreased, meaning that it's moved to the *left* one step.

When they eventually overlap, the loop terminates, and we return `true`

.

Let's say our string is `'racecar'`

, which is a palindrome.

It will go like this:

### Squares of a sorted array example

Another example where we can use the two pointers technique is the problem Squares of a Sorted Array.

The description says:

Given an integer array

`nums`

sorted innon-decreasingorder, returnan array of.the squares of each numbersorted in non-decreasing order

For example, if the input is `[-4, -1, 0, 3, 10]`

, the output should be `[0, 1, 9, 16, 100]`

.

Now obviously, we can just square each one, and then sort the array with a built-in sort method, and be done with it. But a sorting operation is never better than
$O(n \ log \ n)$
runtime, so we can do it using two pointers in just
$O(n)$
time:

```
function sortedSquares(nums: number[]): number[] {
let left = 0;
let right = nums.length - 1;
let result = [];
while (left <= right) {
if (Math.abs(nums[left]) > Math.abs(nums[right])) {
result.push(nums[left++] ** 2);
} else {
result.push(nums[right--] ** 2);
}
}
return result.reverse();
};
```

We compare the absolute value of the items that `left`

and `right`

are pointing to, and push the square of the greater one to our `result`

array. And we return the reversed version of it.

Note |
---|

The reason we return the reversed result is that the array is initially already sorted, and we get the largest absolute value first. The reason that works is related to how two pointers work: as we start from both ends, we initially start with the smallest and largest values in the array. |

Because we only make one pass through the array while comparing, and then later reversing, it ends up being $O(n)$ , a better runtime than $O(n \ log \ n)$ .

The first problem we'll see in this chapter will be Valid Palindrome, which requires a more careful approach than the simplified version shown here.

Until then, happy coding.

## Top comments (0)