Two Pointer Techniques for Array Problems

167. 两数之和 II - 输入有序数组 https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted

167. Two Sum II - Input Array Is Sorted https://leetcode.com/problems/two-sum-ii-input-array-is-sorted

26. 删除有序数组中的重复项 https://leetcode.cn/problems/remove-duplicates-from-sorted-array

26. Remove Duplicates from Sorted Array https://leetcode.com/problems/remove-duplicates-from-sorted-array

27. 移除元素 https://leetcode.cn/problems/remove-element

27. Remove Element https://leetcode.com/problems/remove-element

283. 移动零 https://leetcode.cn/problems/move-zeroes

283. Move Zeroes https://leetcode.com/problems/move-zeroes

344. 反转字符串 https://leetcode.cn/problems/reverse-string

344. Reverse String https://leetcode.com/problems/reverse-string

5. 最长回文子串 https://leetcode.cn/problems/longest-palindromic-substring

5. Longest Palindromic Substring https://leetcode.com/problems/longest-palindromic-substring

83. 删除排序链表中的重复元素 https://leetcode.cn/problems/remove-duplicates-from-sorted-list

83. Remove Duplicates from Sorted List https://leetcode.com/problems/remove-duplicates-from-sorted-list

剑指 Offer 57. 和为s的两个数字 https://leetcode.cn/problems/he-wei-sde-liang-ge-shu-zi-lcof

剑指 Offer 57. 和为s的两个数字 LCOF https://leetcode.com/problems/he-wei-sde-liang-ge-shu-zi-lcof

剑指 Offer II 006. 排序数组中两个数字之和 https://leetcode.cn/problems/kLl5u1

剑指 Offer II 006. 排序数组中两个数字之和 https://leetcode.com/problems/kLl5u1

Note

Now all the plugins has supported English. I'm still improving the website...

This article will resolve

LeetCode	Difficulty
167. Two Sum II - Input Array Is Sorted	🟠
26. Remove Duplicates from Sorted Array	🟢
27. Remove Element	🟢
283. Move Zeroes	🟢
344. Reverse String	🟢
5. Longest Palindromic Substring	🟠
83. Remove Duplicates from Sorted List	🟢

Prerequisites

Before reading this article, you should learn:

• Array Basics
• Array Implementation
• Six Techniques for Solving Single Linked List Problems

When dealing with array and linked list problems, the two-pointer technique is commonly used. This technique mainly falls into two categories: left-right pointers and fast-slow pointers.

Left-right pointers are two pointers moving towards each other or away from each other; fast-slow pointers are two pointers moving in the same direction, one faster than the other.

For single linked lists, most techniques belong to the fast-slow pointer category, as covered in Six Techniques for Solving Single Linked List Problems. For example, detecting a cycle in a linked list or finding the K-th last node in a linked list are problems solved by using a fast pointer and a slow pointer together.

In arrays, there are no actual pointers, but we can treat indices as pointers in the array, allowing us to apply the two-pointer technique. This article mainly discusses array-related two-pointer algorithms.

I. Fast-Slow Pointer Technique

In-Place Modification

A common fast-slow pointer technique in array problems is to modify the array in place.

For example, consider LeetCode problem #26, "Remove Duplicates from Sorted Array," which asks you to remove duplicates from a sorted array:

26. Remove Duplicates from Sorted Array | LeetCode |

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Consider the number of unique elements of nums to be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the unique elements in the order they were present in nums initially. The remaining elements of nums are not important as well as the size of nums.
• Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int[] expectedNums = [...]; // The expected answer with correct length

int k = removeDuplicates(nums); // Calls your implementation

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [1,1,2]
Output: 2, nums = [1,2,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 1 and 2 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4]
Output: 5, nums = [0,1,2,3,4,_,_,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

• 1 <= nums.length <= 3 * 104
• -100 <= nums[i] <= 100
• nums is sorted in non-decreasing order.

The function signature is as follows:

java 🟢

int removeDuplicates(int[] nums);

cpp 🤖

int removeDuplicates(vector<int>& nums);

python 🤖

def removeDuplicates(nums: List[int]) -> int:

go 🤖

func removeDuplicates(nums []int) int {}

javascript 🤖

var removeDuplicates = function(nums) {};

Let's briefly explain what in-place modification means:

If we were not required to modify in place, we could simply create a new int[] array, place the unique elements into this new array, and then return it.

However, the problem requires you to remove duplicates in place, meaning you cannot create a new array. You must work with the original array and return a length. This way, the returned length and the original array will indicate which elements remain after duplicates are removed.

Since the array is already sorted, duplicate elements are adjacent, making them easy to identify. However, if you remove each duplicate element immediately in place, it would involve shifting elements in the array, leading to a time complexity of $O(N^2)$.

To solve this problem efficiently, we use the two-pointer technique:

We let the slow pointer slow trail behind, while the fast pointer fast goes ahead to explore. When fast finds a non-duplicate element, it assigns it to slow and then slow moves forward by one step.

This ensures that nums[0..slow] contains all unique elements. Once the fast pointer has traversed the entire array nums, nums[0..slow] will be the result of the array with duplicates removed.

Here's the code:

java 🟢

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int slow = 0, fast = 0;
        while (fast < nums.length) {
            if (nums[fast] != nums[slow]) {
                slow++;
                // maintain nums[0..slow] with no duplicates
                nums[slow] = nums[fast];
            }
            fast++;
        }
        // the length of the array is index + 1
        return slow + 1;
    }
}

cpp 🤖

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() == 0) {
            return 0;
        }
        int slow = 0, fast = 0;
        while (fast < nums.size()) {
            if (nums[fast] != nums[slow]) {
                slow++;
                // maintain no duplicates in nums[0..slow]
                nums[slow] = nums[fast];
            }
            fast++;
        }
        // the length of the array is index + 1
        return slow + 1;
    }
};

python 🤖

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        slow = 0 
        fast = 1
        while fast < len(nums):
            if nums[fast] != nums[slow]:
                slow += 1
                # maintain nums[0..slow] without duplicates
                nums[slow] = nums[fast]
            fast += 1
        # the length of the array is index + 1
        return slow + 1

go 🤖

func removeDuplicates(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    slow,fast :=0,0
    for fast<len(nums) {
        if nums[fast] != nums[slow] {
            slow++
            // maintain nums[0..slow] with no duplicates
            nums[slow] = nums[fast]
        }
        fast++
    }
    // the length of the array is index + 1
    return slow + 1
}

javascript 🤖

var removeDuplicates = function(nums) {
    if (nums.length == 0) {
        return 0;
    }
    var slow = 0, fast = 0;
    while (fast < nums.length) {
        if (nums[fast] != nums[slow]) {
            slow++;
            // maintain nums[0..slow] with no duplicates
            nums[slow] = nums[fast];
        }
        fast++;
    }
    // the length of the array is index + 1
    return slow + 1;
};

You can refer to the visualization panel to understand the process of algorithm execution:

Let's briefly expand on this. Take a look at LeetCode problem #83, "Remove Duplicates from Sorted List." If you are given a sorted singly linked list, how would you remove the duplicates?

In fact, it is exactly the same as removing duplicates from an array. The only difference is that you change the array assignment operations to pointer operations. Compare it with the previous code:

java 🟢

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        ListNode slow = head, fast = head;
        while (fast != null) {
            if (fast.val != slow.val) {
                // nums[slow] = nums[fast];
                slow.next = fast;
                // slow++;
                slow = slow.next;
            }
            // fast++
            fast = fast.next;
        }
        // disconnect from the following duplicate elements
        slow.next = null;
        return head;
    }
}

cpp 🤖

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr) return nullptr;
        ListNode* slow = head, *fast = head;
        while (fast != nullptr) {
            if (fast->val != slow->val) {
                // nums[slow] = nums[fast];
                slow->next = fast;
                // slow++;
                slow = slow->next;
            }
            // fast++
            fast = fast->next;
        }
        // disconnect from the following duplicate elements
        slow->next = nullptr;
        return head;
    }
};

python 🤖

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if head is None:
            return None
        slow, fast = head, head
        while fast is not None:
            if fast.val != slow.val:
                # nums[slow] = nums[fast];
                slow.next = fast
                # slow++;
                slow = slow.next
            # fast++
            fast = fast.next
        # disconnect from the following duplicate elements
        slow.next = None
        return head

go 🤖

func deleteDuplicates(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    slow, fast := head, head
    for fast != nil {
        if fast.Val != slow.Val {
            // nums[slow] = nums[fast];
            slow.Next = fast
            // slow++;
            slow = slow.Next
        }
        // fast++
        fast = fast.Next
    }
    // disconnect from the following duplicate elements
    slow.Next = nil
    return head
}

javascript 🤖

var deleteDuplicates = function(head) {
    if (head === null) return null;
    let slow = head, fast = head;
    while (fast !== null) {
        if (fast.val !== slow.val) {
            // nums[slow] = nums[fast];
            slow.next = fast;
            // slow++;
            slow = slow.next;
        }
        // fast++
        fast = fast.next;
    }
    // disconnect from the following duplicate elements
    slow.next = null;
    return head;
};

To see the process of the algorithm execution, please refer to the following visualization panel:

Note

Some readers might wonder, "The duplicate elements in the linked list aren't actually removed; they're just left hanging there. Is that appropriate?"

This brings us to the discussion of different language features. Languages like Java and Python, which have garbage collection, can automatically find and reclaim the memory of these "dangling" linked list nodes. However, languages like C++, which lack automatic garbage collection, require us to manually release the memory of these nodes when writing code.

That said, in terms of cultivating algorithmic thinking, it's sufficient to understand this fast-slow pointer technique.

Besides asking you to remove duplicates from sorted arrays/lists, problems might also require you to "remove" certain elements from an array in place.

For example, LeetCode problem #27 "Remove Element". Here's the problem statement:

27. Remove Element | LeetCode |

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

• Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
• Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

• 0 <= nums.length <= 100
• 0 <= nums[i] <= 50
• 0 <= val <= 100

java 🟢

// The function signature is as follows
int removeElement(int[] nums, int val);

cpp 🤖

// The function signature is as follows
int removeElement(vector<int>& nums, int val);

python 🤖

# The function signature is as follows
def removeElement(nums: List[int], val: int) -> int:

go 🤖

// The function signature is as follows
func removeElement(nums []int, val int) int {}

javascript 🤖

// The function signature is as follows
var removeElement = function(nums, val) {};

The problem requires us to remove all elements with the value val from the array nums in place, using the fast and slow pointer technique:

If fast encounters an element with the value val, it skips it. Otherwise, it assigns the value to the slow pointer and moves the slow pointer forward.

This approach is exactly the same as the solution for the array deduplication problem mentioned earlier. Let's directly look at the code:

java 🟢

class Solution {
    public int removeElement(int[] nums, int val) {
        int fast = 0, slow = 0;
        while (fast < nums.length) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
}

cpp 🤖

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int fast = 0, slow = 0;
        while (fast < nums.size()) {
            if (nums[fast] != val) {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
};

python 🤖

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        fast, slow = 0, 0
        while fast < len(nums):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

go 🤖

func removeElement(nums []int, val int) int {
    fast, slow := 0, 0
    for fast < len(nums) {
        if nums[fast] != val {
            nums[slow] = nums[fast]
            slow++
        }
        fast++
    }
    return slow
}

javascript 🤖

var removeElement = function(nums, val) {
    var fast = 0, slow = 0;
    while (fast < nums.length) {
        if (nums[fast] != val) {
            nums[slow] = nums[fast];
            slow++;
        }
        fast++;
    }
    return slow;
}

You can refer to the visualization panel to understand the process of the algorithm execution:

Note that there is a subtle difference from the solution for removing duplicates from a sorted array. Here, we assign nums[slow] first and then increment slow. This ensures that the elements in nums[0..slow-1] do not contain the value val. The length of the resulting array is slow.

After implementing the removeElement function, let's look at LeetCode problem #283, "Move Zeroes":

Given an array nums, modify it in place to move all elements with the value 0 to the end of the array. The function signature is as follows:

java 🟢

void moveZeroes(int[] nums);

cpp 🤖

void moveZeroes(vector<int>& nums);

python 🤖

def moveZeroes(nums: List[int]) -> None:

go 🤖

func moveZeroes(nums []int) {}

javascript 🤖

function moveZeroes(nums) {}

For example, if you are given the input nums = [0,1,4,0,2], your algorithm does not return a value, but it will modify the nums array in place to become [1,4,2,0,0].

Considering the previous questions, do you already have an answer in mind?

You can solve this problem by slightly modifying the removeElement function from the last question, or you can even reuse the removeElement function directly.

The problem asks us to move all zeros to the end, which is essentially the same as removing all zeros from nums and then setting the remaining elements to zero:

java 🟢

class Solution {
    public void moveZeroes(int[] nums) {
        // remove all 0s from nums, return the length of the array without 0s
        int p = removeElement(nums, 0);
        // assign elements of nums[p..] to 0
        for (; p < nums.length; p++) {
            nums[p] = 0;
        }
    }

    public int removeElement(int[] nums, int val) {
        // see the above code implementation
    }
}

cpp 🤖

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        // remove all 0s from nums, return the length of the array without 0s
        int p = removeElement(nums, 0);
        // assign elements of nums[p..] to 0
        for (; p < nums.size(); p++) {
            nums[p] = 0;
        }
    }

    int removeElement(vector<int>& nums, int val) {
        // see the previous code implementation
    }
};

python 🤖

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        # remove all 0 from nums and return the length of the array without 0
        p = self.removeElement(nums, 0)
        # assign elements of nums[p..] to 0
        for i in range(p, len(nums)):
            nums[i] = 0

    def removeElement(self, nums: List[int], val: int) -> int:
        # see the above code implementation

go 🤖

func moveZeroes(nums []int) {
    // remove all 0s from nums and return the length of the array without 0s
    p := removeElement(nums, 0)
    // assign elements of nums[p..] to 0
    for ; p < len(nums); p++ {
        nums[p] = 0
    }
}

func removeElement(nums []int, val int) int {
    // see the implementation in the above code
}

javascript 🤖

var moveZeroes = function(nums) {
    // remove all 0s from nums and return the length of the array without 0s
    var p = removeElement(nums, 0);
    // assign elements of nums[p..] to 0
    for (let i = p; i < nums.length; i++) {
        nums[i] = 0;
    }
};

var removeElement = function(nums, val) {
    // see the above code implementation
};

At this point, we've covered most of the problems involving in-place modification of arrays.

Sliding Window

Another major category of fast-slow pointer problems in arrays is the "Sliding Window Algorithm." In another article, Detailed Explanation of the Sliding Window Algorithm Core Framework, I provide the code framework for the sliding window:

// Pseudocode for the sliding window algorithm framework
int left = 0, right = 0;

while (right < nums.size()) {
    // Expand the window
    window.addLast(nums[right]);
    right++;
    
    while (window needs shrink) {
        // Shrink the window
        window.removeFirst(nums[left]);
        left++;
    }
}

This article won't repeat specific problems. Instead, it emphasizes the fast and slow pointer characteristics of the sliding window algorithm:

The left pointer follows behind, while the right pointer leads ahead. The section between these two pointers forms the "window." The algorithm solves certain problems by expanding and contracting this "window."

II. Common Algorithms Using Left and Right Pointers

Binary Search

In another article Binary Search Framework Explained, I discuss the details of binary search code in depth. Here, I'll only present the simplest binary search algorithm to highlight its dual-pointer characteristics:

java 🟢

int binarySearch(int[] nums, int target) {
    // two pointers, one on the left and one on the right, move towards each other
    int left = 0, right = nums.length - 1;
    while(left <= right) {
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; 
        else if (nums[mid] > target)
            right = mid - 1;
    }
    return -1;
}

cpp 🤖

#include <vector>
using namespace std;

int binarySearch(vector<int>& nums, int target) {
    // two pointers, one on the left and one on the right, move towards each other
    int left = 0, right = nums.size() - 1;
    while(left <= right) {
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; 
        else if (nums[mid] > target)
            right = mid - 1;
    }
    return -1;
}

python 🤖

def binarySearch(nums: List[int], target: int) -> int:
    # two pointers, one on the left and one on the right, move towards each other
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (right + left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        elif nums[mid] > target:
            right = mid - 1

go 🤖

func binarySearch(nums []int, target int) int {
	// two pointers, one on the left and one on the right, moving towards each other
	left, right := 0, len(nums)-1
	for left <= right {
		mid := (right + left) / 2
		if nums[mid] == target {
			return mid
		} else if nums[mid] < target {
			left = mid + 1
		} else if nums[mid] > target {
			right = mid - 1
		}
	}
	return -1
}

javascript 🤖

var binarySearch = function(nums, target) {
    // two pointers, one on the left and one on the right, moving towards each other
    var left = 0;
    var right = nums.length - 1;
    
    while(left <= right) {
        var mid = Math.floor((right + left) / 2);
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; 
        else if (nums[mid] > target)
            right = mid - 1;
    }
    return -1;
}

Sum of n Numbers

Take a look at LeetCode problem 167, "Two Sum II":

167. Two Sum II - Input Array Is Sorted | LeetCode |

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

Constraints:

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

Whenever you have a sorted array, you should think of the two-pointer technique. The solution to this problem is somewhat similar to binary search. By adjusting left and right, you can control the value of sum:

java 🟢

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // one left and one right pointers moving towards each other
        int left = 0, right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                // the index required by the problem starts from 1
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                // make the sum a little bigger
                left++;
            } else if (sum > target) {
                // make the sum a little smaller
                right--;
            }
        }
        return new int[]{-1, -1};
    }
}

cpp 🤖

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        // one pointer on the left and one on the right moving towards each other
        int left = 0, right = numbers.size() - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                // the indices required by the problem start from 1
                return vector<int>{left + 1, right + 1};
            } else if (sum < target) {
                // make the sum a bit larger
                left++;
            } else if (sum > target) {
                // make the sum a bit smaller
                right--;
            }
        }
        return vector<int>{-1, -1};
    }
};

python 🤖

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # one pointer on the left and one on the right moving towards each other
        left, right = 0, len(numbers) - 1
        while left < right:
            sum = numbers[left] + numbers[right]
            if sum == target:
                # the index required by the problem starts from 1
                return [left + 1, right + 1]
            elif sum < target:
                # make the sum a little bigger
                left += 1
            elif sum > target:
                # make the sum a little smaller
                right -= 1
        return [-1, -1]

go 🤖

func twoSum(nums []int, target int) []int {
    // two pointers, one on the left and one on the right, move towards each other
    left, right := 0, len(nums) - 1
    for left < right {
        sum := nums[left] + nums[right]
        if sum == target {
            // the index required by the problem starts from 1
            return []int{left + 1, right + 1}
        } else if sum < target {
            // make the sum a little bigger
            left++
        } else if sum > target {
            // make the sum a little smaller
            right--
        }
    }
    return []int{-1, -1}
}

javascript 🤖

var twoSum = function(nums, target) {
    // two pointers, one on the left and one on the right, move towards each other
    var left = 0, right = nums.length - 1;
    while (left < right) {
        var sum = nums[left] + nums[right];
        if (sum == target) {
            // the index required by the problem starts from 1
            return [left + 1, right + 1];
        } else if (sum < target) {
            // make the sum a bit larger
            left++;
        } else if (sum > target) {
            // make the sum a bit smaller
            right--;
        }
    }
    return [-1, -1];
}

In another article One Function to Solve All nSum Problems, I also used a similar left-right pointer technique to provide a general approach to the nSum problem, which essentially leverages the two-pointer technique.

Reverse Array

Most programming languages provide a reverse function. The principle behind this function is actually very simple. LeetCode problem 344 "Reverse String" is a similar requirement, asking you to reverse a char[] type character array. Let's directly look at the code:

java 🟢

void reverseString(char[] s) {
    // two pointers, one on the left and one on the right, moving towards each other
    int left = 0, right = s.length - 1;
    while (left < right) {
        // swap s[left] and s[right]
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
}

cpp 🤖

void reverseString(vector<char>& s) {
    // two pointers, one on the left and one on the right, move towards each other
    int left = 0, right = s.size() - 1;
    while (left < right) {
        // swap s[left] and s[right]
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
}

python 🤖

def reverseString(s: List[str]) -> None:
    # two pointers, one on the left and one on the right, move towards each other
    left, right = 0, len(s) - 1
    while left < right:
        # swap s[left] and s[right]
        temp = s[left]
        s[left] = s[right]
        s[right] = temp    
        left += 1
        right -= 1

go 🤖

func reverseString(s []rune) {
    // two pointers, one on the left and one on the right, move towards each other
    left, right := 0, len(s)-1
    for left < right {
        // swap s[left] and s[right]
        temp := s[left]
        s[left] = s[right]
        s[right] = temp
        left++
        right--
    }
}

javascript 🤖

var reverseString = function(s) {
    // two pointers, one on the left and one on the right, move towards each other
    var left = 0, right = s.length - 1;
    while (left < right) {
        // swap s[left] and s[right]
        var temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
}

For more advanced problems related to array reversal, you can refer to Creative Traversals of 2D Arrays.

Palindrome Check

A palindrome is a string that reads the same forwards and backwards. For example, the strings aba and abba are palindromes because they are symmetrical and remain the same when reversed. Conversely, the string abac is not a palindrome.

You might now realize that palindrome problems are closely related to the concept of left and right pointers. For instance, if you need to determine whether a string is a palindrome, you can write the following code:

java 🟢

boolean isPalindrome(String s) {
    // two pointers, one on the left and one on the right, move towards each other
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

cpp 🤖

bool isPalindrome(string s) {
    // two pointers, one on the left and one on the right, move towards each other
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

python 🤖

def isPalindrome(s: str) -> bool:
    # two pointers, one on the left and one on the right, moving towards each other
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

go 🤖

func isPalindrome(s string) bool {
    // two pointers, one on the left and one on the right, move towards each other
    left, right := 0, len(s) - 1
    for left < right {
        if s[left] != s[right] {
            return false
        }
        left++
        right--
    }
    return true
}

javascript 🤖

var isPalindrome = function(s) {
    // two pointers, one on the left and one on the right, move towards each other
    var left = 0, right = s.length - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

Next, let's increase the difficulty a bit. Given a string, can you use the two-pointer technique to find the longest palindrome substring within it?

This is LeetCode problem #5, "Longest Palindromic Substring":

5. Longest Palindromic Substring | LeetCode |

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

• 1 <= s.length <= 1000
• s consist of only digits and English letters.

The function signature is as follows:

java 🟢

String longestPalindrome(String s);

cpp 🤖

string longestPalindrome(string s);

python 🤖

def longestPalindrome(s: str):

go 🤖

func longestPalindrome(s string) string {}

javascript 🤖

var longestPalindrome = function(s) {
};

The challenge in finding palindromic substrings lies in the fact that the length of a palindrome can be either odd or even. The key to solving this problem is the two-pointer technique that expands from the center to both ends.

If the length of the palindrome is odd, it has a single center character; if the length is even, it can be considered to have two center characters. Therefore, we can start by implementing a function like this:

java 🟢

// Find the longest palindrome centered with s[l] and s[r] in s
String palindrome(String s, int l, int r) {
    // prevent index out of bounds
    while (l >= 0 && r < s.length()
            && s.charAt(l) == s.charAt(r)) {
        // two pointers, expand to both sides
        l--; r++;
    }
    // return the longest palindrome centered with s[l] and s[r]
    return s.substring(l + 1, r);
}

cpp 🤖

// Find the longest palindrome centered with s[l] and s[r] in s
std::string palindrome(std::string s, int l, int r) {
    // Prevent index out of bounds
    while (l >= 0 && r < s.length()
            && s[l] == s[r]) {
        // Two pointers expand to both sides
        l--; r++;
    }
    // Return the longest palindrome centered with s[l] and s[r]
    return s.substr(l + 1, r-l-1);
}

python 🤖

# Find the longest palindrome in s with s[l] and s[r] as the center
def palindrome(s: str, l: int, r: int) -> str:
    # Prevent index out of bounds
    while l >= 0 and r < len(s) and s[l] == s[r]:
        # Two pointers, expand to both sides
        l -= 1
        r += 1
    # Return the longest palindrome with s[l] and s[r] as the center
    return s[l + 1: r]

go 🤖

// Find the longest palindrome in s with s[l] and s[r] as the center
func palindrome(s string, l int, r int) string {
    // Prevent index out of bounds
    for l >= 0 && r < len(s) && s[l] == s[r] {
        // Two pointers, expand to both sides
        l--
        r++
    }
    // Return the longest palindrome with s[l] and s[r] as the center
    return s[l+1 : r]
}

javascript 🤖

var palindrome = function(s, l, r) {
    // find the longest palindrome in s with s[l] and s[r] as the center
    // prevent index out of bounds
    while (l >= 0 && r < s.length
            && s.charAt(l) == s.charAt(r)) {
        // two pointers, expand to both sides
        l--; r++;
    }
    // return the longest palindrome with s[l] and s[r] as the center
    return s.substring(l + 1, r);
}

This way, if you input the same l and r, it means you are looking for a palindrome of odd length. If you input adjacent l and r, it means you are looking for a palindrome of even length.

Now, coming back to the problem of finding the longest palindrome, the general approach is:

for 0 <= i < len(s):
    Find the palindrome centered at s[i]
    Find the palindrome centered at s[i] and s[i+1]
    Update the answer

Translating this into code can solve the problem of finding the longest palindromic substring:

java 🟢

String longestPalindrome(String s) {
    String res = "";
    for (int i = 0; i < s.length(); i++) {
        // the longest palindrome substring with s[i] as the center
        String s1 = palindrome(s, i, i);
        // the longest palindrome substring with s[i] and s[i+1] as the centers
        String s2 = palindrome(s, i, i + 1);
        // res = longest(res, s1, s2)
        res = res.length() > s1.length() ? res : s1;
        res = res.length() > s2.length() ? res : s2;
    }
    return res;
}

cpp 🤖

string longestPalindrome(string s) {
    string res = "";
    for (int i = 0; i < s.length(); i++) {
        // the longest palindromic substring centered at s[i]
        string s1 = palindrome(s, i, i);
        // the longest palindromic substring centered at s[i] and s[i+1]
        string s2 = palindrome(s, i, i + 1);
        // res = longest(res, s1, s2)
        res = res.length() > s1.length() ? res : s1;
        res = res.length() > s2.length() ? res : s2;
    }
    return res;
}

python 🤖

def longestPalindrome(s: str) -> str:
    res = ""
    for i in range(0, len(s)):
        # the longest palindrome substring centered at s[i]
        s1 = palindrome(s, i, i)
        # the longest palindrome substring centered at s[i] and s[i+1]
        s2 = palindrome(s, i, i + 1)
        # res = longest(res, s1, s2)
        res = s1 if len(res) < len(s1) else res
        res = s2 if len(res) < len(s2) else res
    return res

go 🤖

func longestPalindrome(s string) string {
    var res string
    for i := 0; i < len(s); i++ {
        // the longest palindromic substring centered at s[i]
        s1 := palindrome(s, i, i)
        // the longest palindromic substring centered at s[i] and s[i+1]
        s2 := palindrome(s, i, i+1)
        // res = longest(res, s1, s2)
        if len(res) < len(s1) {
            res = s1
        }
        if len(res) < len(s2) {
            res = s2
        }
    }
    return res
}

javascript 🤖

var longestPalindrome = function(s) {
    var res = "";
    for (var i = 0; i < s.length; i++) {
        // the longest palindrome substring centered at s[i]
        var s1 = palindrome(s, i, i);
        // the longest palindrome substring centered at s[i] and s[i+1]
        var s2 = palindrome(s, i, i + 1);
        // res = longest(res, s1, s2)
        res = res.length > s1.length ? res : s1;
        res = res.length > s2.length ? res : s2;
    }
    return res;
}

You might notice that the left and right pointers used in finding the longest palindromic substring differ from those in previous problems: in previous problems, the pointers move towards each other from both ends, whereas in the palindromic substring problem, the pointers expand outwards from the center. However, this situation is specific to palindrome problems, so I still categorize it under left and right pointers.

With this, we have covered all the two-pointer techniques related to arrays. For more extensions and practice problems, see More Classic and Frequent Array Two-Pointer Problems.

---

Related Problems

You can install my Chrome extension then open the link.

LeetCode	Difficulty
1. Two Sum	🟢
125. Valid Palindrome	🟢
131. Palindrome Partitioning	🟠
267. Palindrome Permutation II🔒	🟠
281. Zigzag Iterator🔒	🟠
42. Trapping Rain Water	🔴
543. Diameter of Binary Tree	🟢
658. Find K Closest Elements	🟠
75. Sort Colors	🟠
80. Remove Duplicates from Sorted Array II	🟠
82. Remove Duplicates from Sorted List II	🟠
9. Palindrome Number	🟢

---