Two Pointer Techniques for Array Problems

When dealing with array and linked list problems, the two-pointer technique is often used. It mainly includes two types: left-right pointers and fast-slow pointers.

The left-right pointers move toward each other or away from each other; the fast-slow pointers move in the same direction, with one moving faster than the other.

For singly linked lists, most techniques involve fast-slow pointers. The Six Linked List Problem-Solving Patterns cover these, such as detecting cycles in a linked list, finding the Kth node from the end, etc., where a fast pointer and a slow pointer work together to complete the task.

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

1. Fast-Slow Pointer Technique

In-Place Modification

A common use of the 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," where you are asked to remove duplicates in a sorted array:

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];
}

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

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

The function signature is as follows:

int removeDuplicates(int[] nums);

int removeDuplicates(vector<int>& nums);

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

func removeDuplicates(nums []int) int {}

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:

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;
    }
}

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;
    }
};

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

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
}

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;
};

Let's extend this a bit and look at LeetCode Problem 83, "Remove Duplicates from Sorted List". If you have a sorted singly linked list, how would you remove duplicates?

It's actually identical to removing duplicates from an array. The only difference is replacing array assignment operations with pointer manipulations. Compare with the previous code:

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;
    }
}

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;
    }
};

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

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
}

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;
};

The execution process of the algorithm can be seen in the visualization panel below:

Apart from removing duplicates in a sorted array/linked list, problems may also require "in-place deletion" of certain elements in an array.

For example, LeetCode problem 27 "Remove Element", let's take a look at the problem:

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];
}

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

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

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

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

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

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

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

The problem requires us to remove all elements with the value val from 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 slow forward.

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

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;
    }
}

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;
    }
};

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

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

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

Note that there is a subtle difference between this solution and the one for removing duplicates from a sorted array: here, we first assign a value to nums[slow] and then increment slow. This ensures that nums[0..slow-1] does not contain elements with the value val, and the final length of the resulting array is slow.

After implementing the removeElement function, let's take a look at LeetCode Problem 283, "Move Zeroes":

You are given an input array nums, and you need to modify it in-place to move all elements with the value 0 to the end of the array. The function signature is as follows:

void moveZeroes(int[] nums);

void moveZeroes(vector<int>& nums);

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

func moveZeroes(nums []int) {}

function moveZeroes(nums) {}

For example, if you input nums = [0,1,4,0,2], your algorithm should not return a value but modify the nums array in-place to [1,4,2,0,0].

Considering the problems mentioned earlier, do you already have an answer?

By slightly modifying the removeElement function from the previous problem, you can solve this one as well, or you can directly reuse the removeElement function.

The problem requires us to move all 0s to the end, which is essentially equivalent to removing all 0s from nums and then assigning 0 to the elements at the end:

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
    }
}

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
    }
};

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

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
}

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 have almost covered the problems related to in-place array modifications.

Sliding Window

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

// 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++;
    }
}

Specific problems are not repeated in this article; instead, it emphasizes the fast and slow pointer characteristics of the sliding window algorithm:

The left pointer trails, the right pointer leads, and the part between the two pointers is the "window." The algorithm solves certain problems by expanding and shrinking this "window."

II. Common Algorithms with Left and Right Pointers

Binary Search

In another article, Detailed Explanation of Binary Search Framework, I explored the details of binary search code. Here, I only present the simplest binary search algorithm to highlight its double pointer feature:

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;
}

#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;
}

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
    return -1

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
}

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;
}

n Sum Problem

Consider LeetCode Problem 167, "Two Sum II":

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

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

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

As long as the array is sorted, the double pointer technique should come to mind. The solution to this problem is somewhat similar to binary search, where adjusting left and right can change the size of sum:

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};
    }
}

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};
    }
};

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]

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}
}

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, A Function to Solve All nSum Problems, I also apply a similar left and right pointer technique to provide a general approach to the nSum problem, essentially utilizing the double pointer technique.

Reversing an Array

Most programming languages provide a reverse function. The principle of this function is straightforward. LeetCode Problem 344, "Reverse String," requires you to reverse a char[] type character array. Let's look at the code:

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--;
    }
}

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--;
    }
}

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

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--
    }
}

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 on array reversal, refer to Fancy Traversal 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 read the same in both directions. Conversely, the string abac is not a palindrome.

Now, you should see that palindrome problems are closely related to the two-pointer technique. For instance, to check if a string is a palindrome, you can write the following code:

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;
}

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;
}

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

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
}

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, to increase the difficulty, given a string, use the two-pointer technique to find the longest palindrome within it. Can you do it?

This is LeetCode Problem 5: Longest Palindromic Substring:

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

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

The function signature is as follows:

String longestPalindrome(String s);

string longestPalindrome(string s);

def longestPalindrome(s: str):

func longestPalindrome(s string) string {}

var longestPalindrome = function(s) {
};

The challenge in finding a palindrome is that its length can be either odd or even. The key to solving this problem is the two-pointer technique that expands from the center.

If the palindrome's length is odd, it has a single center character; if even, it can be considered to have two center characters. Thus, we can first implement this function:

// 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++;
    }

    // now [l+1, r-1] is the longest palindrome string
    return s.substring(l + 1, r);
}

// 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++;
    }
    // now [l+1, r-1] is the longest palindrome string
    return s.substr(l + 1, r-l-1);
}

# 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
    # now [l+1, r-1] is the longest palindrome string
    return s[l + 1: r]

// 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++
    }
    // now [l+1, r-1] is the longest palindrome string
    return s[l+1 : r]
}

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++;
    }

    // now [l+1, r-1] is the longest palindrome string
    return s.substring(l + 1, r);
}

In this way, if the input l and r are the same, it finds palindromes of odd length; if l and r are adjacent, it finds palindromes of even length.

Returning to the longest palindrome problem, the general approach is:

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

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

class Solution {
    public 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;
    }

    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)) {
            // expand to both sides
            l--;
            r++;
        }
        // now [l+1, r-1] is the longest palindrome string
        return s.substring(l + 1, r);
    }
}

#include <string>
using namespace std;

class Solution {
public:
    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;
    }

private:
    string palindrome(string s, int l, int r) {
        // prevent index out of bounds
        while (l >= 0 && r < s.length() && s[l] == s[r]) {
            // expand to both sides
            l--;
            r++;
        }
        // now [l+1, r-1] is the longest palindrome string
        return s.substr(l + 1, r - l - 1);
    }
};

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

    def palindrome(self, s: str, l: int, r: int) -> str:
        # prevent index out of bounds
        while l >= 0 and r < len(s) and s[l] == s[r]:
            # expand to both sides
            l -= 1
            r += 1
        # now [l+1, r-1] is the longest palindrome string
        return s[l + 1:r]

func longestPalindrome(s string) string {
    res := ""
    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 = res
        } else {
            res = s1
        }
        if len(res) > len(s2) {
            res = res
        } else {
            res = s2
        }
    }
    return res
}

func palindrome(s string, l, r int) string {
    // prevent index out of bounds
    for l >= 0 && r < len(s) && s[l] == s[r] {
        // expand to both sides
        l--
        r++
    }
    // now [l+1, r-1] is the longest palindrome string
    return s[l+1:r]
}

var longestPalindrome = function(s) {
    let res = "";
    for (let i = 0; i < s.length; i++) {
        // the longest palindromic substring centered at s[i]
        let s1 = palindrome(s, i, i);
        // the longest palindromic substring centered at s[i] and s[i+1]
        let 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;
};

var palindrome = function(s, l, r) {
    // prevent index out of bounds
    while (l >= 0 && r < s.length && s[l] === s[r]) {
        // expand to both sides
        l--;
        r++;
    }
    // now [l+1, r-1] is the longest palindrome string
    return s.substring(l + 1, r);
};

You may notice that the two-pointer technique used in the longest palindromic substring problem differs from previous problems: previously, the pointers moved towards each other from both ends, whereas in the palindrome problem, they expand outward from the center. However, such cases mainly occur in palindrome problems, so I include them under the two-pointer category.

This concludes the two-pointer techniques related to arrays. For more extensions and applications, see More Classic and High-Frequency Two-Pointer Problems in Arrays.