01. Two Pointer#

Theory#

The two-pointer technique scans a sequence with two indices instead of nested loops — typically O(n) time, O(1) extra space.

Recognition signals#

Signal	Pointer style	Examples
Sorted array + pair sum	Opposite ends (`lo`, `hi`)	LC 167, 15 (3Sum)
In-place partition / remove	Same direction (`slow`, `fast`)	LC 26, 27, 283
Palindrome check	Opposite ends on string/list	LC 125
Linked list cycle / middle	Fast/slow (see Pattern 02)	LC 141, 876
Container with most water	Opposite ends, move shorter side	LC 11

Tradeoff: two pointers on sorted data vs hash map — pointers O(1) space; hash map O(n) space but works on unsorted input (LC 1 vs LC 167).

Description#

The Two Pointer Pattern is a technique used to solve problems involving sequences (such as arrays or lists) by utilizing two pointers that traverse the sequence in different ways. This approach is particularly effective in optimizing performance by reducing time complexity, especially for problems that involve checking pairs, subarrays, or in-place rearrangements.

This technique should be your go-to when you see a question that involves searching for a pair (or more!) of elements in an array that meet a certain criteria, or when you need to compact or partition a sequence in one pass.

Problems at a glance#

LC	Problem
26	1. Remove Duplicates from Sorted Array	↗
922	2. Sort Array By Parity II	↗
75	3. Sort Colors	↗
151	4. Reverse Words in a String	↗
125	1. Valid Palindrome	↗
1	2. Two Sum	↗
11	3. Container With Most Water	↗
15	4. 3Sum	↗
16	5. Three Sum Closest	↗
611	6. Valid Triangle Number	↗
942	7. DI String Match	↗
948	8. Bag of Tokens	↗
1813	9. Sentence Similarity III	↗

Types#

Same Direction #

When to Use

This technique is ideal for problems like finding unique elements, removing duplicates in-place, rearranging elements, or scanning a string sequentially.

How It Works

One pointer (typically called slow) moves through the array, while the other pointer (called fast) explores further elements.
The slow pointer often keeps track of the current valid position, while the fast pointer scans for new valid elements.
This is especially useful for in-place compaction and partitioning problems.

1. Remove Duplicates from Sorted Array (Leetcode:26)#

Problem Statement

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.

Return k after placing the final result in the first k slots of nums.

Example 1:

Input: nums = [1,1,2] Output: 2, nums = [1,2,_]

Example 2:

Input: nums = [0,0,1,1,1,2,2,3,3,4] Output: 5, nums = [0,1,2,3,4,,,,,_]

Constraints:

1 <= nums.length <= 3 * 10^4 -10^4 <= nums[i] <= 10^4 nums is sorted in non-decreasing order.

Code and Explanation

Approach 1

from typing import List

def removeDuplicates(nums: List[int]) -> int:
    if not nums:
        return 0

    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]

    return slow + 1

Explanation:

Initialization:
- slow = 0: Index of the last unique element written so far.
Scan with fast:
- For each fast from 1 to n - 1, if nums[fast] != nums[slow], we found a new unique value.
- Increment slow and copy nums[fast] into nums[slow].
Return:
- The number of unique elements is slow + 1.

Time: O(n) · Space: O(1)

2. Sort Array By Parity II (Leetcode:922)#

Problem Statement

Given an array of integers nums, half of the integers in nums are odd, and the other half are even. Sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even. Return any answer array that satisfies this condition.

Example 1:

Input: nums = [4,2,5,7] Output: [4,5,2,7] Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Example 2:

Input: nums = [2,3] Output: [2,3]

Constraints:

2 <= nums.length <= 2 * 10^4 nums.length is even. Half of the integers in nums are even. 0 <= nums[i] <= 1000

Follow Up:

Could you solve it in-place?

Code and Explanation

Approach 1Approach 2

from typing import List

def sortArrayByParityII(nums: List[int]) -> List[int]:
    even, odd = 0, 1
    n = len(nums)

    while even < n and odd < n:
        if nums[even] % 2 == 0:
            even += 2
        elif nums[odd] % 2 == 1:
            odd += 2
        else:
            nums[even], nums[odd] = nums[odd], nums[even]
            even += 2
            odd += 2

    return nums

Explanation:

Initialization:
- even = 0, odd = 1: Pointers to the next even and odd indices respectively.
Loop through array:
- If the element at even is already even, advance even by 2.
- Else if the element at odd is already odd, advance odd by 2.
- Else swap the misplaced values and advance both pointers by 2.
Return result:
- The array is rearranged in-place so even indices hold even numbers and odd indices hold odd numbers.

from typing import List

def sortArrayByParityII(nums: List[int]) -> List[int]:
    evens = [x for x in nums if x % 2 == 0]
    odds = [x for x in nums if x % 2 == 1]

    res = [0] * len(nums)
    res[0::2] = evens
    res[1::2] = odds

    return res

Explanation:

Split values:
- Separate even and odd numbers into two lists.
Interleave:
- Fill even indices with evens and odd indices with odds.
Return result:
- Works but uses O(n) extra space; Approach 1 is the in-place solution.

3. Sort Colors (Leetcode:75)#

Problem Statement

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively. You must solve this problem without using the library's sort function.

Example 1:

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

Example 2:

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

Constraints:

n == nums.length 1 <= n <= 300 nums[i] is either 0, 1, or 2.

Follow Up: Could you come up with a one-pass algorithm using only constant extra space?

Code and Explanation

Approach 1

from typing import List

def sortColors(nums: List[int]) -> None:
    low, mid, high = 0, 0, len(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

Explanation:
Dutch National Flag algorithm — three pointers in one pass.

Initialization:
- low: next position for 0.
- mid: current element under inspection.
- high: next position for 2.
Partition:
- 0 → swap with low, advance both low and mid.
- 1 → already in the middle region, advance mid.
- 2 → swap with high, shrink high (do not advance mid yet).
Result:
- Array is sorted as [0...0, 1...1, 2...2] in O(n) time and O(1) space.

4. Reverse Words in a String (Leetcode:151)#

Problem Statement

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue" Output: "blue is sky the"

Example 2:

Input: s = " hello world " Output: "world hello" Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good example" Output: "example good a" Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints:

1 <= s.length <= 10^4 s contains English letters, digits, and spaces. There is at least one word in s.

Code and Explanation

Approach 1Approach 2

def reverseWords(s: str) -> str:
    res = []
    left = len(s) - 1

    while left >= 0:
        while left >= 0 and s[left] == " ":
            left -= 1
        if left < 0:
            break

        right = left
        while left >= 0 and s[left] != " ":
            left -= 1

        res.append(s[left + 1:right + 1])

    return " ".join(res)

Explanation:

Scan from the end:
- left starts at the last character and moves backward.
Extract each word:
- Skip spaces, mark right at the end of a word, then move left to the start of that word.
- Append the substring to res.
Return result:
- Join extracted words with a single space. Both pointers move in the same direction (right to left).

def reverseWords(s: str) -> str:
    return " ".join(s.split()[::-1])

Explanation:

s.split() removes extra spaces and splits into words.
[::-1] reverses the word list.
" ".join(...) rebuilds the sentence. Concise but less illustrative of pointer mechanics.

Opposite End#

When to Use

This technique is ideal for problems where you need to find pairs that satisfy a specific condition, such as a target sum or maximum area, especially in sorted arrays or when moving inward from both ends shrinks the search space.

How It Works

One pointer starts at the beginning (left) and the other at the end (right).
Both pointers move toward each other, adjusting based on the condition being checked.
If the sum is too low, move left forward; if too high, move right backward.
For area problems, always move the pointer at the shorter boundary.

1. Valid Palindrome (Leetcode:125)#

Problem Statement

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward.

Given a string s, return true if it is a palindrome, or false otherwise.

Example 1:

Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome.

Example 2:

Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome.

Constraints:

1 <= s.length <= 2 * 10^5 s consists only of printable ASCII characters.

Code and Explanation

Approach 1

def isPalindrome(s: str) -> bool:
    left, right = 0, len(s) - 1

    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1

        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True

Explanation:

Initialization:
- left = 0, right = len(s) - 1: pointers at opposite ends.
Skip non-alphanumeric characters:
- Advance left or shrink right until both point to alphanumeric chars.
Compare:
- If lowercase versions differ, return False.
- Otherwise move both pointers inward.
Return:
- If the loop completes, the string is a palindrome.

Time: O(n) · Space: O(1)

2. Two Sum (Leetcode:1)#

Problem Statement

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6 Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6 Output: [0,1]

Constraints:

2 <= nums.length <= 10^4 -10^9 <= nums[i] <= 10^9 -10^9 <= target <= 10^9 Only one valid answer exists.

Follow Up:

Can you come up with an algorithm that is less than O(n^2) time complexity?

Code and Explanation

Approach 1Approach 2

from typing import List

def twoSum(nums: List[int], target: int) -> List[int]:
    paired = [(num, i) for i, num in enumerate(nums)]
    paired.sort(key=lambda x: x[0])

    left, right = 0, len(paired) - 1
    while left < right:
        current_sum = paired[left][0] + paired[right][0]
        if current_sum == target:
            return [paired[left][1], paired[right][1]]
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    raise ValueError("No two sum solution found")

Explanation:

Pair values with indices:
- Store (value, original_index) so we can return original positions after sorting.
Sort by value:
- Enables the opposite-ends two-pointer search (same idea as LC 167).
Two-pointer search:
- If sum equals target, return indices.
- If sum is too small, move left right; if too large, move right left.
Tradeoff:
- O(n log n) time, O(n) space for the paired list. Works on unsorted input after sorting.

from typing import List

def twoSum_hashmap(nums: List[int], target: int) -> List[int]:
    num_map = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in num_map:
            return [num_map[complement], i]
        num_map[num] = i

Explanation:

Single pass with hash map:
- For each num, check if target - num was seen before.
Return immediately:
- As soon as the complement exists, return both indices.
Tradeoff:
- O(n) time and O(n) space; preferred when the array is unsorted and you cannot sort (e.g., need original order constraints). Not a two-pointer solution, but the standard optimal approach for LC 1.

3. Container With Most Water (Leetcode:11)#

Problem Statement

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:

Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The max area of water the container can contain is 49.

Example 2:

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

Constraints:

n == height.length 2 <= n <= 10^5 0 <= height[i] <= 10^4

Code and Explanation

Approach 1

from typing import List

def maxArea(height: List[int]) -> int:
    left, right = 0, len(height) - 1
    max_area = 0

    while left < right:
        h = min(height[left], height[right])
        w = right - left
        max_area = max(max_area, h * w)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_area

Explanation:

Initialization:
- left = 0, right = len(height) - 1, max_area = 0.
Compute area:
- Area is limited by the shorter line: min(height[left], height[right]) * (right - left).
Greedy move:
- Move the pointer at the shorter line inward — keeping the taller line gives the only chance to find a larger area.
Return:
- max_area after all valid pairs are considered in O(n) time.

4. 3Sum (Leetcode:15)#

Problem Statement

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: The distinct triplets are [-1,0,1] and [-1,-1,2].

Example 2:

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

Example 3:

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

Constraints:

3 <= nums.length <= 3000 -10^5 <= nums[i] <= 10^5

Code and Explanation

Approach 1

from typing import List

def threeSum(nums: List[int]) -> List[List[int]]:
    nums.sort()
    res = []

    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue

        left, right = i + 1, len(nums) - 1

        while left < right:
            curr_sum = nums[i] + nums[left] + nums[right]

            if curr_sum == 0:
                res.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif curr_sum < 0:
                left += 1
            else:
                right -= 1

    return res

Explanation:

Sort:
- Sorting enables two-pointer search for the remaining two values.
Fix first element:
- Loop i over the array; skip duplicate values of nums[i].
Two-pointer pair search:
- With left = i + 1 and right = n - 1, adjust pointers based on whether the sum is below, above, or equal to 0.
Skip duplicates:
- After finding a triplet, skip duplicate left and right values to avoid repeated triplets.
Complexity:
- O(n²) time, O(1) extra space (excluding output).

5. Three Sum Closest (Leetcode:16)#

Problem Statement

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1 Output: 2 Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:

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

Constraints:

3 <= nums.length <= 500 -1000 <= nums[i] <= 1000 -10^4 <= target <= 10^4

Code and Explanation

Approach 1

from typing import List

def threeSumClosest(nums: List[int], target: int) -> int:
    nums.sort()
    n = len(nums)
    closest_sum = float('inf')

    for i in range(n - 2):
        left, right = i + 1, n - 1

        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]

            if abs(current_sum - target) < abs(closest_sum - target):
                closest_sum = current_sum

            if current_sum < target:
                left += 1
            elif current_sum > target:
                right -= 1
            else:
                return current_sum

    return closest_sum

Explanation:

Sort the array:
- Same setup as 3Sum — fix one element, search the rest with two pointers.
Track closest sum:
- Update closest_sum whenever current_sum is nearer to target.
Pointer movement:
- If sum is too small, move left right; if too large, move right left; if exact match, return immediately.
Return:
- After all triplets are checked, return the closest sum found.

Time: O(n²) · Space: O(1)

6. Valid Triangle Number (Leetcode:611)#

Problem Statement

Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Example 1:

Input: nums = [2,2,3,4] Output: 3 Explanation: Valid combinations are (2,3,4) with either 2, and (2,2,3).

Example 2:

Input: nums = [4,2,3,4] Output: 4

Constraints: 1 <= nums.length <= 1000 0 <= nums[i] <= 1000

Code and Explanation

Approach 1

from typing import List

def triangleNumber(nums: List[int]) -> int:
    nums.sort()
    count = 0

    for i in range(len(nums) - 1, 1, -1):
        left, right = 0, i - 1
        while left < right:
            if nums[left] + nums[right] > nums[i]:
                count += right - left
                right -= 1
            else:
                left += 1

    return count

Explanation:

Sort the array:
- After sorting, triangle inequality reduces to nums[left] + nums[right] > nums[i] when nums[i] is the largest side.
Fix largest side:
- Iterate i from right to left, treating nums[i] as the largest side.
Two-pointer search:
- If the sum of the two smaller sides exceeds nums[i], all pairs between left and right - 1 also work — add right - left to the count.
Return:
- Total count of valid triangles.

7. DI String Match (Leetcode:942)#

Problem Statement

A permutation perm of n + 1 integers of all the integers in the range [0, n] can be represented as a string s of length n where:

s[i] == 'I' if perm[i] < perm[i + 1], and s[i] == 'D' if perm[i] > perm[i + 1].

Given a string s, reconstruct the permutation perm and return it. If there are multiple valid permutations perm, return any of them.

Example 1:

Input: s = "IDID" Output: [0,4,1,3,2]

Example 2:

Input: s = "III" Output: [0,1,2,3]

Example 3:

Input: s = "DDI" Output: [3,2,0,1]

Constraints:

1 <= s.length <= 10^5 s[i] is either 'I' or 'D'.

Code and Explanation

Approach 1

def diStringMatch(s: str) -> list[int]:
    low, high = 0, len(s)
    res = []
    for ch in s:
        if ch == 'I':
            res.append(low)
            low += 1
        else:
            res.append(high)
            high -= 1
    res.append(low)
    return res

Explanation:

Two ends of the number pool:
- low and high track the smallest and largest unused numbers.
Greedy assignment:
- On 'I', pick the smallest remaining number (low).
- On 'D', pick the largest remaining number (high).
Append last number:
- After processing s, exactly one number remains (low == high).
Return:
- A valid permutation in O(n) time.

8. Bag of Tokens (Leetcode:948)#

Problem Statement

You start with an initial power of power, an initial score of 0, and a bag of tokens given as an integer array tokens, where each tokens[i] denotes the value of tokeni.

Your goal is to maximize the total score by strategically playing these tokens. In one move, you can play an unplayed token in one of the two ways (but not both for the same token):

Face-up: If your current power is at least tokens[i], you may play tokeni, losing tokens[i] power and gaining 1 score. Face-down: If your current score is at least 1, you may play tokeni, gaining tokens[i] power and losing 1 score.

Return the maximum possible score you can achieve after playing any number of tokens.

Example 1:

Input: tokens = [100], power = 50 Output: 0

Example 2:

Input: tokens = [200,100], power = 150 Output: 1

Example 3:

Input: tokens = [100,200,300,400], power = 200 Output: 2

Constraints:

0 <= tokens.length <= 1000 0 <= tokens[i], power < 10^4

Code and Explanation

Approach 1

from typing import List

def bagOfTokensScore(tokens: List[int], power: int) -> int:
    tokens.sort()
    left, right = 0, len(tokens) - 1
    score = max_score = 0

    while left <= right:
        if power >= tokens[left]:
            power -= tokens[left]
            score += 1
            left += 1
            max_score = max(max_score, score)
        elif score > 0:
            power += tokens[right]
            score -= 1
            right -= 1
        else:
            break

    return max_score

Explanation:

Sort tokens:
- Use smallest tokens face-up to gain score cheaply; use largest face-down to recover power.
Two pointers:
- left for face-up plays, right for face-down plays.
Greedy loop:
- Play face-up while possible and track max_score.
- If stuck, trade one score for power via face-down on the largest remaining token.
Return:
- Maximum score achievable.

9. Sentence Similarity III (Leetcode:1813)#

Problem Statement

You are given two strings sentence1 and sentence2, each representing a sentence composed of words. Two sentences are similar if one can become the other by inserting a single sentence (possibly empty) at some position.

Given two sentences sentence1 and sentence2, return true if they are similar. Otherwise, return false.

Example 1:

Input: sentence1 = "My name is Haley", sentence2 = "My Haley" Output: true

Example 2:

Input: sentence1 = "of", sentence2 = "A lot of words" Output: false

Example 3:

Input: sentence1 = "Eating right now", sentence2 = "Eating" Output: true

Constraints:

1 <= sentence1.length, sentence2.length <= 100

Code and Explanation

Approach 1Approach 2

def areSentencesSimilar(sentence1: str, sentence2: str) -> bool:
    w1 = sentence1.split()
    w2 = sentence2.split()

    if len(w1) < len(w2):
        w1, w2 = w2, w1

    i = 0
    while i < len(w2) and w1[i] == w2[i]:
        i += 1

    j = 0
    while j < len(w2) - i and w1[-(j + 1)] == w2[-(j + 1)]:
        j += 1

    return i + j >= len(w2)

Explanation:

Split into words:
- Ensure w1 is the longer sentence.
Match prefix:
- Advance i while words match from the start.
Match suffix:
- Advance j while words match from the end (without overlapping the prefix).
Similarity check:
- If every word in the shorter sentence matched at the start or end, the middle gap is the inserted sentence — return True.

from collections import deque

def areSentencesSimilar_deque(sentence1: str, sentence2: str) -> bool:
    dq1 = deque(sentence1.split())
    dq2 = deque(sentence2.split())

    while dq1 and dq2 and dq1[0] == dq2[0]:
        dq1.popleft()
        dq2.popleft()

    while dq1 and dq2 and dq1[-1] == dq2[-1]:
        dq1.pop()
        dq2.pop()

    return len(dq1) == 0 or len(dq2) == 0

Explanation:

Deque variant:
- Same prefix/suffix logic, but peel matching words from both ends using deques.
Return:
- If either deque is empty, all words of the shorter sentence aligned with the longer one.