Coding Interview Patterns: Two Pointers

Table of Contents

Introduction

The two pointers pattern is a technique that allows us to efficiently traverse or manipulate sequential data structures, such as arrays or linked lists. As the name implies, this involves using two pointers that traverse a data structure in a coordinated way, starting from different positions or moving in opposite directions.

These pointers adjust dynamically based on specific conditions, enabling efficient data exploration and optimal time and space complexity. When needing to find two elements in an array that meet a certain condition, the two pointer pattern should be the go to strategy.

Depending on the problem, pointers can iterate in one or both directions. For example, to check if a string is a palindrome, one pointer can start from the beginning and another from the end, comparing values at each step to verify palindrome properties.

When to use it?

To determine if your problem is a match for the two pointer pattern, consider the following criteria:

1. Comparing Elements: If the problem involves comparing elements in a data structure (like an array or a string) to find pairs that satisfy a certain condition, the two pointer technique might be suitable.

2. Single or Opposite Directions: If the problem can benefit from traversing the data structure in one or both directions simultaneously, it’s a good indicator that the two pointer pattern is applicable.

3. Optimal Efficiency: If the problem requires an efficient solution in terms of time and space complexity, the two pointer technique often provides a way to achieve this, especially when compared to brute force methods.

4. Sorted Data: Many problems that use the two pointer technique involve sorted data, although this is not a strict requirement. Sorting can often simplify the implementation and improve efficiency.

Example Code: isPalindrome

Consider a problem where you need to determine whether a given string is a palindrome. A palindrome is a string that reads the same forward and backward when ignoring non-alphanumeric characters and case differences. For instance, “A man, a plan, a canal: Panama” is a palindrome, while “race a car” is not.

function isPalindrome(s: string): boolean {
	// Remove special characters e.g. #@.&%$?¡
	s = s.trim().toLowerCase().replace(/[^a-zA-Z0-9]/g, '')

	// Define two pointers to traverse the string.
	let l = 0, r = s.length - 1

	while(l < r) {
		// If at some point the characters at the left and right pointers are not
		// equal, returns `false`.
		if (s[l] !== s[r]) {
			return false
		}

		// Move both pointers and continue evaluating the string.
		l++
		r--
	}

	// If we reach to this point, it means the string is a valid palindrome.
	return true
}

Big O Notation Analysis

The isPalindrome function checks whether a given string is a palindrome by using a two pointer technique. Let’s analyze its time and space complexity.

Time Complexity

Since each character in the string is processed at most once, the overall time complexity is O(n), where n is the length of the string.

Space Complexity

The function does not use any additional space that grows with the input size, so the space complexity is O(1).

Conclusion

If your problem involves comparing elements, traversing in one or both directions, and requires efficient solutions, the two pointer pattern is likely a good match. Consider the nature of your data and the specific requirements of the problem to determine the applicability of this technique.