Algorithms — Two Pointers Template That Solves Many Problems

Discussing Two Pointers algorithm, and how to use its template code to solve multiple interview questions in C# for a deeper understanding of Data Structure and Algorithms.

Goal

The goal is to share some concise notes on the Two Pointers algorithm at the high-level and its typical use cases or relevant interview questions. Hopefully, this allows you to add it to your tool bag without getting swamped by detailed textbook explanations. The following items are covered:

• Algorithm high-level logic
• Typical use cases/interview questions referencing LeetCode
• Typical bugs/gotchas in implementation

Three types of Two Pointers

Depending on the starting point of the two pointers, left (L) and right (R):

• Same Direction
• Opposite Direction
• Facing Direction

Image by Author

Facing Direction Use Cases

Below are some typical use cases and frequently asked interview questions on Two Pointers with facing direction.

Use Case 1 — Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. See LeetCode link for full description.

Image by author

Notes:

• O(n) time complexity
• O(1) space complexity
• Bug free: must check for null input
• Bug free: must ensure pointers/indexes are not out of bound

Sample implementation in C#:

Follow-up questions:

• Consider non-alphabetic and non-digit chars

Use Case 2 — Valid Palindrome II

Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome. See full details on LeetCode link.

Image by author

Sample implementation in C#:

Follow-up questions:

• Similar code both running two pointers
• How to improve code reuse by introducing a FindDifference() method

Use Case 3 — Two Sum

Given an array of integers, numbers, and an integer target, return the two numbers such that they add up to target. See full details on LeetCode link, note LeetCode requires indexes to be returned, which is a follow-up question here.

This classic Two Sum question has two common solutions:

1. Dictionary: O(n) time, O(n) space
2. Two Pointers Facing Direction: O(nlogn) time, O(1) space

Image by author

Sample implementation using both Dictionary and Two Pointers in C#:

Follow-up questions:

• Which algorithm is better is the array is sorted? Two pointers.
• What if the indexes of the two numbers need to be returned? Dictionary.

Best Practices for Bug Free Code

• Input validation
  - string input: null check, empty “” check
  - object input: null check
• Index validation
  - out of bound check
• Object property and object method
  - null check on the object
• Avoid global variables

Summary

Two Pointers is a great algorithm that typically gives you a solution with O(N) time complexity and O(1) space complexity. We have looked at its applications using two pointers facing each other for:

• Valid Palindrome
• Valid Palindrome II
• Two Sum (classic)

The sample code comes from a GitHub repository that hosts a collection of algorithms most frequently asked in code interviews. This repo is actively being developed.

Many thanks for reading!