Skip to content

Two Pointers

First PublishedByAtif Alam

Difficulty: Easy. ROI: High.

Other common names: Two-pointer technique, dual pointers.

When to use: Use when you need to find pairs in a sorted array, check for a target sum, or traverse from both ends of a sequence (e.g. palindrome check, in-place operations).

Idea: Maintain two indices (left and right, or one per sequence) and move them based on a condition so each step makes progress and you avoid a full nested loop.

Time / space: Often O(n) time, O(1) extra space when iterating in place.

Example #1 — Two sum in sorted array

Section titled “Example #1 — Two sum in sorted array”

Given a sorted array and a target value, determine whether any two elements sum to the target. Two pointers at the start and end let us adjust the current sum by moving inward (smaller sum → move left right; larger sum → move right left).

Sample input and output

arr = [1, 2, 4, 6, 10]
print(two_sum_sorted(arr, 8))   # True  (pair 2, 6)
print(two_sum_sorted(arr, 15))  # False (no pair sums to 15)
  • Sample input: arr = [1, 2, 4, 6, 10], target = 8.
  • Sample output: True — the pair (2, 6) sums to 8. For target = 15 the output is False (no pair sums to 15).

Code (with inline comments)

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1  # start from both ends
    while left < right:
        current_sum = arr[left] + arr[right]  # sum of current pair
        if current_sum == target:
            return True
        if current_sum < target:
            left += 1   # sum too small → move left right for a larger value
        if current_sum > target:
            right -= 1  # sum too large → move right left for a smaller value
    return False

Line-by-line:

  • left, right = 0, len(arr) - 1 — We put one pointer at the start and one at the end of the array. Because the array is sorted, moving left right gives a larger value and moving right left gives a smaller value.
  • while left < right: — We stop when the pointers meet; by then we’ve considered every pair that could include one element from the left and one from the right.
  • current_sum = arr[left] + arr[right] — Current pair’s sum.
  • if current_sum == target: return True — Found a pair that sums to the target.
  • if current_sum < target: left += 1 — The sum is too small. Any pair using the current left with a node to the left of right would be even smaller, so we increase the sum by moving left right to a larger element.
  • if current_sum > target: right -= 1 — The sum is too large. We decrease it by moving right left to a smaller element.
  • return False — No pair summed to the target.

Execution trace (numbered list)

Trace for arr = [1, 2, 4, 6, 10], target = 8. Initially left=0, right=4.

  1. Step 1: left=0, right=4, current_sum=11 → 11 > 8, so right -= 1.
  2. Step 2: left=0, right=3, current_sum=7 → 7 < 8, so left += 1.
  3. Step 3: left=1, right=3, current_sum=8 → 8 == 8, return True.

Execution trace (code with step comments)

Below is the same run written as code: we update left/right, compute current_sum, and take the action. The comments record the trace at each step.

arr = [1, 2, 4, 6, 10]
target = 8
left, right = 0, len(arr) - 1


# Step 1
current_sum = arr[left] + arr[right]   # 1 + 10 = 11
# 11 > 8 → right -= 1
right -= 1


# Step 2
current_sum = arr[left] + arr[right]   # 1 + 6 = 7
# 7 < 8 → left += 1
left += 1


# Step 3
current_sum = arr[left] + arr[right]   # 2 + 6 = 8
# 8 == 8 → return True
# (in the real function we would return True here)

Execution trace (ASCII diagram)

At each step, L and R show the two pointers; we compute current_sum and then move one pointer.

Step 1:  [ 1,  2,  4,  6, 10 ]
          L               R
         current_sum = 11 > 8  →  right -= 1


Step 2:  [ 1,  2,  4,  6, 10 ]
          L        R
         current_sum = 7 < 8  →  left += 1


Step 3:  [ 1,  2,  4,  6, 10 ]
              L     R
         current_sum = 8 == 8  →  return True

Example #2 — Container with most water

Section titled “Example #2 — Container with most water”

Given an array of heights (each index is a vertical line), find two lines that form a container (with the x-axis as the bottom) holding the most water. Area = min(height[left], height[right]) × (right - left). Two pointers at both ends; move the shorter side inward (only moving the shorter can increase the minimum and possibly the area).

Sample input and output

heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
print(max_area(heights))  # 49  (lines at index 1 and 8)
  • Sample input: heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
  • Sample output: 49 — lines at index 1 (height 8) and index 8 (height 7), width 7, area = min(8,7)×7 = 49.

Code (with inline comments)

def max_area(heights):
    left, right = 0, len(heights) - 1  # two pointers at both ends
    best = 0
    while left < right:
        width = right - left           # distance between the two lines
        area = min(heights[left], heights[right]) * width  # water height = shorter line
        best = max(best, area)
        if heights[left] <= heights[right]:
            left += 1   # move shorter side inward (only this can possibly increase area)
        else:
            right -= 1
    return best

Line-by-line:

  • left, right = 0, len(heights) - 1 — Two pointers at the start and end of the array. Each index is a vertical line; we’ll consider all pairs of lines.
  • best = 0 — We’ll keep the maximum area we’ve seen so far.
  • width = right - left — The horizontal distance between the two lines (number of steps between them).
  • area = min(heights[left], heights[right]) * width — The water level is limited by the shorter line, so the area is that height times the width.
  • best = max(best, area) — Update the best area if this container is larger.
  • if heights[left] <= heights[right]: left += 1 — Move the shorter side inward. Moving the taller side inward can only shrink the container (width goes down, and the minimum height won’t increase). Moving the shorter side might let us find a taller line and a better area.
  • else: right -= 1 — Same idea: the right line is shorter, so we move right left.
  • return best — Return the maximum area we found.

Execution trace (numbered list)

Trace for heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]. Initially left=0, right=8.

  1. Step 1: left=0, right=8, area=min(1,7)×8=8, best=8. Height 1 ≤ 7 → left += 1.
  2. Step 2: left=1, right=8, area=min(8,7)×7=49, best=49. Height 8 > 7 → right -= 1.
  3. Step 3: left=1, right=7, area=min(8,3)×6=18, best=49. Height 8 > 3 → right -= 1.
  4. (Further steps shrink the window; best remains 49.) Final answer: 49.

Execution trace (code with step comments)

heights = [1, 8, 6, 2, 5, 4, 8, 3, 7]
left, right = 0, len(heights) - 1
best = 0


# Step 1
width = right - left   # 8
area = min(heights[left], heights[right]) * width   # min(1,7)*8 = 8
best = max(best, area)  # 8
# height 1 <= 7 → left += 1
left += 1


# Step 2
width = right - left   # 7
area = min(heights[left], heights[right]) * width   # min(8,7)*7 = 49
best = max(best, area)  # 49
# height 8 > 7 → right -= 1
right -= 1
# ... more steps; best stays 49

Execution trace (ASCII diagram)

L and R are the two lines; area = min(height at L, height at R) × width.

Step 1:  [ 1,  8,  6,  2,  5,  4,  8,  3,  7 ]
          L                               R
         area = min(1,7)×8 = 8   →  left += 1


Step 2:  [ 1,  8,  6,  2,  5,  4,  8,  3,  7 ]
              L                           R
         area = min(8,7)×7 = 49  →  right -= 1  (best = 49)

Example #3 — Valid palindrome

Section titled “Example #3 — Valid palindrome”

Check if a string is a palindrome after ignoring non-alphanumeric characters and case. Two pointers at start and end; skip non-alphanumeric, compare (case-insensitive), then move both inward.

Sample input and output

s = "A man, a plan, a canal: Panama"
print(is_palindrome(s))  # True
  • Sample input: s = "A man, a plan, a canal: Panama"
  • Sample output: True — alphanumeric sequence is “amanaplanacanalpanama”, which reads the same forward and backward.

Code (with inline comments)

def is_palindrome(s):
    left, right = 0, len(s) - 1  # start from both ends
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1   # skip non-alphanumeric from the left
        while left < right and not s[right].isalnum():
            right -= 1  # skip non-alphanumeric from the right
        if s[left].lower() != s[right].lower():
            return False  # mismatch → not a palindrome
        # match → move both inward
        left += 1
        right -= 1
    return True

Line-by-line:

  • left, right = 0, len(s) - 1 — Two pointers at the start and end of the string. We’ll compare characters as we move them inward.
  • while left < right: — Continue until the pointers meet or cross; by then we’ve checked all pairs that matter.
  • while left < right and not s[left].isalnum(): left += 1 — isalnum() returns True if the character is a letter or digit. We skip any non-alphanumeric character (spaces, punctuation) from the left until we find one to compare.
  • while left < right and not s[right].isalnum(): right -= 1 — Same from the right: skip non-alphanumeric characters.
  • if s[left].lower() != s[right].lower(): return False — lower() makes the comparison case-insensitive. If the two characters don’t match, the string is not a palindrome.
  • left += 1; right -= 1 — The characters match, so we move both pointers inward and continue.
  • return True — We compared all relevant pairs and they matched.

Execution trace (numbered list)

Trace for s = "A man, a plan, a canal: Panama". We skip spaces/punctuation and compare only letters (case-insensitive).

  1. Step 1: left moves to ‘A’, right skips to ‘a’ (end). Compare ‘a’ vs ‘a’ → match, left+=1, right-=1.
  2. Step 2: left skips to ‘m’, right to ‘m’. Match, move both inward.
  3. (Continue inward; all pairs match.) Return True.

Execution trace (code with step comments)

s = "A man, a plan, a canal: Panama"
left, right = 0, len(s) - 1
# Skip non-alphanumeric: left → 'A', right → 'a'
# Compare 'a' == 'a' → match, left += 1, right -= 1
# Repeat until left >= right → return True

Execution trace (ASCII diagram)

L and R move inward, skipping non-alphanumeric; we compare only when both point at alphanumeric characters.

After skips:  "A man, a plan, a canal: Panama"
               L                          R
              'A' vs 'a' (lower) → match, move both inward
              ... repeat until L and R meet

Example #4 — Reverse a string (in-place)

Section titled “Example #4 — Reverse a string (in-place)”

Reverse the string in place using O(1) extra space. Two pointers at start and end; swap and move inward until they meet.

Sample input and output

s = list("hello")
reverse_string(s)
print(s)  # ['o', 'l', 'l', 'e', 'h']
  • Sample input: s = list("hello") (caller passes a mutable list)
  • Sample output: After the call, s is ['o', 'l', 'l', 'e', 'h']. In Python, strings are immutable, so the problem is often given with a list of characters; if you need to return a new string, use ''.join(s) after reversing.

Code (with inline comments)

def reverse_string(s):
    # s is a list of chars (e.g. from list(s)) so we can modify in place
    left, right = 0, len(s) - 1  # two pointers at both ends
    while left < right:
        s[left], s[right] = s[right], s[left]  # swap
        left += 1
        right -= 1   # move both inward

Line-by-line:

  • s is a list of chars — In Python, strings are immutable (you can’t change them in place). So we take a list of characters (e.g. from list(s)); the caller must pass a mutable list if we’re to reverse in place.
  • left, right = 0, len(s) - 1 — Two pointers at the first and last index. We’ll swap and move them toward the center.
  • while left < right: — Stop when they meet or cross; we’ve then swapped every pair.
  • s[left], s[right] = s[right], s[left] — Swap the two characters at the current positions in one statement.
  • left += 1; right -= 1 — Move both pointers inward so we swap the next pair on the next iteration.

Execution trace (numbered list)

Trace for s = list("hello") (indices 0..4). Initially left=0, right=4.

  1. Step 1: Swap s[0] and s[4] → ['o', 'e', 'l', 'l', 'h']. left=1, right=3.
  2. Step 2: Swap s[1] and s[3] → ['o', 'l', 'l', 'e', 'h']. left=2, right=2.
  3. left >= right → stop. Result: ['o', 'l', 'l', 'e', 'h'] (reversed).

Execution trace (code with step comments)

s = list("hello")   # ['h', 'e', 'l', 'l', 'o']
left, right = 0, len(s) - 1  # 0, 4


# Step 1: swap s[0] and s[4]
s[left], s[right] = s[right], s[left]  # ['o', 'e', 'l', 'l', 'h']
left += 1   # 1
right -= 1  # 3


# Step 2: swap s[1] and s[3]
s[left], s[right] = s[right], s[left]  # ['o', 'l', 'l', 'e', 'h']
left += 1   # 2
right -= 1  # 2
# left >= right → done

Execution trace (ASCII diagram)

L and R swap and move inward until they meet.

Initial:  [ 'h', 'e', 'l', 'l', 'o' ]
            L                   R
Step 1:   swap → [ 'o', 'e', 'l', 'l', 'h' ]
                L           R
Step 2:   swap → [ 'o', 'l', 'l', 'e', 'h' ]
                    L   R
Done (L >= R)

Real-world use cases (SRE perspective)

Section titled “Real-world use cases (SRE perspective)”

Two pointers often shows up in SRE and platform work when you have ordered data or need to compare or pair things from opposite ends:

  • Logs and time-series — Events or metrics sorted by time: find pairs of timestamps that bracket a window, or two ranges that sum to a target (e.g. “two periods whose combined error count equals X”). Same idea as two sum in a sorted array.
  • Config and drift — Compare two sorted lists (e.g. expected vs actual config keys, or two versions of a host list) with one pointer per list to find first difference, common prefix, or to merge/deduplicate. Validating that a config snippet is “symmetric” (e.g. balanced brackets or palindromic structure) is the same pattern as valid palindrome.
  • Intervals and windows — Merge overlapping maintenance windows, alert windows, or availability ranges: sort by start (or end), then walk with two pointers to merge or find max overlap. “Container with most water”–style reasoning applies when you care about a pair of boundaries and a quantity (e.g. capacity between two timestamps).
  • Strings and payloads — Check if a log line, webhook payload, or serialized config is well-formed (palindrome-like checks), or normalize/reverse a buffer in place when parsing or transforming without extra allocation.
  • Resource and capacity — Pair “demand” and “supply” when both are sorted (e.g. by size or time): two pointers, one per list, to match or find a valid pair in O(n).