Two Pointers

Overview

Each pointer represents an index or position within a data structure. With two pointers, we enable efficient comparisons and traversals that would otherwise require nested loops.

When to Use

• Linear data structure (arrays, strings, linked lists)
• Input follows a predictable pattern (e.g., sorted array, palindromic string)
• Problem asks for a pair or range of values
• Need to compare elements from different positions

Traversal Strategies

Inward Traversal

Pointers start at opposite ends and move toward each other.

 L                   R
 ↓                   ↓
[1,  2,  3,  4,  5,  6]
 ╰─────→     ←──────╯

• Movement: Both pointers move each iteration (one from left, one from right)
• Ideal for: Comparing elements from both ends, palindromes, sorted array pair finding

Unidirectional Traversal

Both pointers start at the same end and move in the same direction.

 W   R
 ↓   ↓
[0,  1,  0,  3,  12]
 ╰───────────────→

• Movement: Both pointers move forward, but at different rates or conditions
• Ideal for: In-place array modification, partitioning elements

Problems

Pair Sum – Sorted

Given an array of integers sorted in ascending order and a target value, return the indexes of any pair of numbers in the array that sum to the target. The order of the indexes in the result doesn't matter. If no pair is found, return an empty array.

Example 1:

Input: nums = [-5, -2, 3, 4, 6], target = 7
Output: [2, 3]

Explanation: nums[2] + nums[3] = 3 + 4 = 7

Example 2:

Input: nums = [1, 1, 1], target = 2
Output: [0, 1]

Explanation: other valid outputs could be [1, 0], [0, 2], [2, 0], [1, 2] or [2, 1].

Brute Force Approach

Checking all possible pairs using two nested loops. An outer loop traverses for the first number of the pair, an inner loop traverses the rest of the array for the second number of the pair.

This approach has a time complexity of O(n^2), and doesn't take into account the fact that the input is sorted.

Two Pointers Approach

For any value at left and right:

• If their sum is less than the target, move left right.
• If their sum is greater than the target, move right left.
• If their sum is equal to the target, return [left, right].

Complexity:

• Time complexity: O(n).
• Space complexity: O(1).

Interviewing Tips

• Consider all information provided. The key insight is that the input is sorted.

Triplet Sum

Given an array of integers, return all triplets [a, b, c] (values, not indexes) such that a + b + c = 0. The solution must not contain duplicate triplets (e.g., [1, 2, 3] and [2, 3, 1] are considered duplicates). If no such triplets are found, return an empty array.

Example 1:

Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]

Explanation: nums[0] + nums[2] + nums[3] = -1 + 1 + 2 = 0 and nums[0] + nums[1] + nums[4] = -1 + 0 + 1 = 0.

Example 2:

Input: nums = [0, 0, 0, 0]
Output: [[0, 0, 0]]

Explanation: Only one unique triplet sums to zero, despite multiple valid index combinations.

Brute Force Approach

Check all possible triplets using three nested loops. For each combination of three elements, check if their sum equals zero.

This approach has a time complexity of O(n³) and doesn't leverage sorting to eliminate duplicates efficiently.

Two Pointers Approach

Sort the array first, then fix one element a and use pair sum to find b + c = -a from the remaining elements:

• For each a, set left to the element after a and right to the end.
• If a + left + right < 0, move left right.
• If a + left + right > 0, move right left.
• If a + left + right = 0, record the triplet and move both pointers.

Optimizations:

• Skip duplicate values of a to avoid duplicate triplets.
• Skip duplicate values of b or c within the pair sum.
• Stop when a becomes positive (triplets summing to 0 cannot be formed with all positive numbers).

Complexity:

• Time complexity: O(n²) — Sort costs O(n log n), then for each element, pair sum costs O(n).
• Space complexity: O(n) for sorting (depends on implementation).

Interviewing Tips

• Clarify whether the output should contain values or indexes.
• Ask about handling duplicates in both input and output.

Is Palindrome Valid

Given a string, determine if it's a palindrome after removing all non-alphanumeric characters. A character is alphanumeric if it's either a letter or a number.

Example 1:

Input: s = "a dog! a panic in a pagoda"
Output: true

Explanation: After removing non-alphanumeric characters: "adogapanicainapagoda", which reads the same forwards and backwards.

Example 2:

Input: s = "abc123"
Output: false

Explanation: After removing non-alphanumeric characters: "abc123", which is not a palindrome.

Brute Force Approach

Create a new string with only alphanumeric characters (lowercased), then compare it with its reverse.

This approach has a time complexity of O(n) but uses O(n) extra space for the filtered string and its reverse.

Two Pointers Approach

A palindrome is identical when read left to right and right to left. Use inward traversal, skipping non-alphanumeric characters:

• Start left at the beginning, right at the end.
• Skip non-alphanumeric characters by moving each pointer inward.
• Compare characters (case-insensitive). If they differ, return false.
• Move both pointers inward and repeat until they meet.

Complexity:

• Time complexity: O(n).
• Space complexity: O(1).

Interviewing Tips

• Clarify constraints: presence of non-alphanumeric characters, their treatment, role of numbers, case sensitivity.
• Confirm before using significant built-in functions (e.g., isalnum, regex).

Largest Container

You are given an array of numbers, each representing the height of a vertical line on a graph. A container can be formed with any pair of these lines, along with the x-axis of the graph. Return the amount of water the largest container can hold.

Example 1:

Input: heights = [2, 7, 8, 3, 7, 6]
Output: 24

Explanation: The container formed between index 1 (height 7) and index 4 (height 7) has width 3 and height 7, giving min(7, 7) * (4 - 1) = 21. The optimal container is between index 1 and index 5: min(7, 6) * 4 = 24.

Example 2:

Input: heights = [1, 1]
Output: 1

Explanation: The only container possible has width 1 and height 1.

Brute Force Approach

Check all possible pairs of lines and calculate the water each container can hold. Track the maximum.

This approach has a time complexity of O(n²).

Two Pointers Approach

For two vertical lines, the water contained is min(heights[i], heights[j]) * (j - i). The minimum height is used because water above it would overflow.

• Start left at the beginning, right at the end.
• Calculate water for current container and update maximum.
• Move the pointer pointing to the shorter line inward.
• Repeat until pointers meet.

Why move the shorter line? Moving the taller line can only decrease or maintain the width while the height is still limited by the shorter line. Moving the shorter line gives a chance to find a taller line.

Complexity:

• Time complexity: O(n).
• Space complexity: O(1).

Interviewing Tips

• Clarify whether heights can be zero or negative.
• Explain the greedy insight: moving the shorter line is optimal because keeping it limits potential area.

Shift Zeros to End

Given an array of integers, modify the array in place to move all zeros to the end while maintaining the relative order of non-zero elements.

Example 1:

Input:  nums = [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]

Explanation: All zeros are moved to the end while 1, 3, 12 maintain their relative order.

Example 2:

Input:  nums = [0, 0, 1]
Output: [1, 0, 0]

Explanation: The single non-zero element moves to the front.

Brute Force Approach

Build a new array by first collecting all non-zero elements, then appending zeros to fill the remaining positions. Copy the result back to the original array.

This approach has a time complexity of O(n) but uses O(n) extra space.

Two Pointers Approach

Use the reader-writer pattern (unidirectional traversal). The reader scans through the array, while writer tracks where the next non-zero should go:

• Both pointers start at the beginning.
• When reader finds a non-zero, swap it with the element at writer, then advance writer.
• Always advance reader.

Complexity:

• Time complexity: O(n).
• Space complexity: O(1).

Interviewing Tips

• Clarify whether in-place modification is required or if extra space is allowed.
• Ask about the expected ratio of zeros to non-zeros (affects number of swaps).

Next Lexicographical Sequence

Given a string of lowercase English letters, rearrange the characters to form a new string representing the next immediate sequence in lexicographical (alphabetical) order. If the given string is already last in lexicographical order among all possible arrangements, return the arrangement that's first in lexicographical order.

Example 1:

Input:  s = "abcd"
Output: "abdc"

Explanation: The next permutation after "abcd" swaps c and d.

Example 2:

Input:  s = "dcba"
Output: "abcd"

Explanation: "dcba" is the last permutation, so we wrap around to the first: "abcd".

Brute Force Approach

Generate all permutations of the string, sort them lexicographically, find the current string, and return the next one (or the first if current is last).

This approach has a time complexity of O(n! × n) which is impractical for any reasonable input size.

Two Pointers Approach

This problem uses multiple pointer passes to find the next permutation in O(n) time:

1. Find the pivot: Scan from right to find the rightmost character that breaks the non-increasing sequence.
2. Handle edge case: If no pivot found, the string is already the last sequence — reverse and return.
3. Find successor: Find the rightmost character greater than the pivot.
4. Swap: Swap the pivot with its successor to increase lexicographical order.
5. Minimize suffix: Use two pointers to reverse the suffix after the pivot (making it the smallest permutation).

Complexity:

• Time complexity: O(n).
• Space complexity: O(n) for the character array, O(1) if modifying in place.

Interviewing Tips

• Be precise with terminology: it's "non-increasing" (allows equal), not "decreasing" (strictly less).
• Walk through an example step-by-step to demonstrate understanding of the algorithm.