DZone
Thanks for visiting DZone today,
Edit Profile
  • Manage Email Subscriptions
  • How to Post to DZone
  • Article Submission Guidelines
Sign Out View Profile
  • Post an Article
  • Manage My Drafts
Over 2 million developers have joined DZone.
Log In / Join
Please enter at least three characters to search
Refcards Trend Reports
Events Video Library
Refcards
Trend Reports

Events

View Events Video Library

Zones

Culture and Methodologies Agile Career Development Methodologies Team Management
Data Engineering AI/ML Big Data Data Databases IoT
Software Design and Architecture Cloud Architecture Containers Integration Microservices Performance Security
Coding Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks
Culture and Methodologies
Agile Career Development Methodologies Team Management
Data Engineering
AI/ML Big Data Data Databases IoT
Software Design and Architecture
Cloud Architecture Containers Integration Microservices Performance Security
Coding
Frameworks Java JavaScript Languages Tools
Testing, Deployment, and Maintenance
Deployment DevOps and CI/CD Maintenance Monitoring and Observability Testing, Tools, and Frameworks

Last call! Secure your stack and shape the future! Help dev teams across the globe navigate their software supply chain security challenges.

Modernize your data layer. Learn how to design cloud-native database architectures to meet the evolving demands of AI and GenAI workloads.

Releasing software shouldn't be stressful or risky. Learn how to leverage progressive delivery techniques to ensure safer deployments.

Avoid machine learning mistakes and boost model performance! Discover key ML patterns, anti-patterns, data strategies, and more.

Related

  • Generics in Java and Their Implementation
  • Commonly Occurring Errors in Microsoft Graph Integrations and How To Troubleshoot Them (Part 4)
  • Mule 4 DataWeave(1.x) Script To Resolve Wildcard Dynamically
  • Mule 3 DataWeave(1.x) Script To Resolve Wildcard Dynamically

Trending

  • Why High-Performance AI/ML Is Essential in Modern Cybersecurity
  • Building Enterprise-Ready Landing Zones: Beyond the Initial Setup
  • Revolutionizing Financial Monitoring: Building a Team Dashboard With OpenObserve
  • AWS to Azure Migration: A Cloudy Journey of Challenges and Triumphs
  1. DZone
  2. Data Engineering
  3. Data
  4. The Two-Pointers Technique

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.

By 
Sergei Golitsyn user avatar
Sergei Golitsyn
·
Feb. 21, 23 · Tutorial
Likes (4)
Comment
Save
Tweet
Share
7.1K Views

Join the DZone community and get the full member experience.

Join For Free

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

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

Java
 
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

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

Java
 
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

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

Java
 
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. 

Data structure Java (programming language) Strings Data Types Use case

Opinions expressed by DZone contributors are their own.

Related

  • Generics in Java and Their Implementation
  • Commonly Occurring Errors in Microsoft Graph Integrations and How To Troubleshoot Them (Part 4)
  • Mule 4 DataWeave(1.x) Script To Resolve Wildcard Dynamically
  • Mule 3 DataWeave(1.x) Script To Resolve Wildcard Dynamically

Partner Resources

×

Comments
Oops! Something Went Wrong

The likes didn't load as expected. Please refresh the page and try again.

ABOUT US

  • About DZone
  • Support and feedback
  • Community research
  • Sitemap

ADVERTISE

  • Advertise with DZone

CONTRIBUTE ON DZONE

  • Article Submission Guidelines
  • Become a Contributor
  • Core Program
  • Visit the Writers' Zone

LEGAL

  • Terms of Service
  • Privacy Policy

CONTACT US

  • 3343 Perimeter Hill Drive
  • Suite 100
  • Nashville, TN 37211
  • support@dzone.com

Let's be friends:

Likes
There are no likes...yet! 👀
Be the first to like this post!
It looks like you're not logged in.
Sign in to see who liked this post!