Two Pointers

Authors: @heiheihang @wingkwong

Overview

The two pointers technique is a technique used to iterate through a data set, typically an array or a list, in a controlled way. It involves using two pointers, one pointing to the beginning of the data set and the other pointing to the end, and moving them towards each other based on specific conditions. This technique is commonly used to solve problems that involve searching for a specific condition or pattern within a data set, or that require a comparison between different elements in the data set.

The two pointers technique is mainly used for solving problems that have a linear time complexity, it can lead to substantial performance improvements over a brute-force approach. Some common examples of problems that can be solved using this technique include:

Finding the maximum / minimum value in a set of data.
Counting the number of occurrences of a specific element.
Finding the longest substring without repeating characters.
Finding the maximum sum of a sub-array of size $k$ .

Overall, the two pointers technique is a useful approach for solving specific types of problems that involve iterating through a data set in a controlled way, such as in pattern matching, data analysis, and statistics. It allows for an efficient and controlled iteration of a data set, which can lead to improved performance and more accurate results.

Example 1: 977. Squares of a Sorted Array

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.

Let's look at this example

# input
nums = [-4,-1,0,3,10]

From this input, we can generate the following square numbers:

squares = [16, 1, 0, 9, 100]

We want to return the following sorted squares:

answer = [0, 1, 9, 16, 100]

You may be thinking, why can't we generate the squares and then sort the result? This approach would take $O(NlogN)$ , and we want to do better than this.

We can sequentially add the next biggest elements with the two pointer approach. We first set a left_pointer at the left of the list and a right_pointer at the right of the list. The left_pointer should be pointing at the largest negative number (most negative), and the right_pointer should be pointing at the largest positive number. We can move the pointers accordingly to find the next largest squared number.

Python
C++
Java

Written by @heiheihang

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        # initialize two pointers
        left_pointer, right_pointer = 0, len(nums) - 1
        # initialize result
        res = []
        # while left_pointer does not meet right_pointer
        while(left_pointer <= right_pointer):
            # if the square of left_pointer and right_pointer 
            if(abs(nums[left_pointer]) > abs(nums[right_pointer])):
                res.append(nums[left_pointer] ** 2)
                # we move the left to the right
                left_pointer += 1
            else:
                res.append(nums[right_pointer] ** 2)
                # we move the right pointer to the left
                right_pointer -= 1
        # we need to reverse the result list
        res.reverse()
        return res

Written by @wingkwong

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int left_pointer = 0;
        int right_pointer = nums.size() - 1;
        vector<int> res;
        while(left_pointer <= right_pointer) {
            if(abs(nums[left_pointer]) > abs(nums[right_pointer])) {
                res.push_back(nums[left_pointer] * nums[left_pointer]);
                left_pointer += 1;
            }
            else {
                res.push_back(nums[right_pointer] * nums[right_pointer]);
                right_pointer -= 1;
            }
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

Written by @wingkwong

class Solution {
    public List<Integer> sortedSquares(int[] nums) {
        int left_pointer = 0;
        int right_pointer = nums.length - 1;
        List<Integer> res = new ArrayList<>();
        while(left_pointer <= right_pointer) {
            if(Math.abs(nums[left_pointer]) > Math.abs(nums[right_pointer])) {
                res.add(nums[left_pointer] * nums[left_pointer]);
                left_pointer += 1;
            }
            else {
                res.add(nums[right_pointer] * nums[right_pointer]);
                right_pointer -= 1;
            }
        }
        Collections.reverse(res);
        return res;
    }
}

Unfortunately, there is no fixed way to perform two pointers. However, generally, we have a pointer at the start of the list and another pointer at the end of the list. We have to carefully analyze the question and choose the most appropriate approach to operate the two pointers.

Problem Name	Difficulty	Solution Link
1768 - Merge Strings Alternately	Easy	View Solutions
2108 - Find First Palindromic String in the Array	Easy	View Solutions
0283 - Move Zeroes	Easy	View Solutions

Overview​

Example 1: 977. Squares of a Sorted Array

Suggested Problems

Overview