The Two-Pointers Technique

Aloha, 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[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] 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.