Identifying Two Pointer Subproblem

When the Problem Is Bigger Than One Two-Pointer Pass

So far, we’ve seen problems where a single two-pointer traversal solves the whole thing. But some problems are too complex for that — they consist of multiple smaller pieces, and the two-pointer technique applies to one (or more) of those pieces.

The key shift in thinking:

Instead of asking “can I solve this with two pointers?”, ask “can I decompose this into subproblems, any of which can be solved with two pointers?”

The Diagnostic Questions

If yes to both, you have a two-pointer subproblem pattern problem.

The Example: Rotate an Array k Times Left

Problem: Given an array arr of size n and an integer k, rotate the array k positions to the left in-place.

Input:  arr = [1, 2, 3, 4, 5, 6, 7, 8],  k = 4
Output: arr = [5, 6, 7, 8, 1, 2, 3, 4]

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart LR
  subgraph BEFORE["Before  (k=4)"]
    direction LR
    A["1"] --- B["2"] --- C["3"] --- D["4"] --- E["5"] --- F["6"] --- G["7"] --- H["8"]
  end
  subgraph AFTER["After rotating 4 left"]
    direction LR
    I["5"] --- J["6"] --- K["7"] --- L["8"] --- M["1"] --- N["2"] --- O["3"] --- P["4"]
  end
  BEFORE -->|"rotate left by k=4"| AFTER

Rotate an array k=4 times to the left — the first 4 elements wrap around to the end.

Brute Force: Temp Array, O(n) Space

Copy elements at k-shifted indices into a temp array, then copy back:

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  subgraph ORIG["Original:  [1, 2, 3, 4, 5, 6, 7, 8]"]
    direction LR
    A1["1"] --- B1["2"] --- C1["3"] --- D1["4"] --- E1["5"] --- F1["6"] --- G1["7"] --- H1["8"]
  end
  subgraph TEMP["Temp:  temp[i] = arr[(i+k) % n]"]
    direction LR
    A2["5"] --- B2["6"] --- C2["7"] --- D2["8"] --- E2["1"] --- F2["2"] --- G2["3"] --- H2["4"]
  end
  subgraph COPY["Copy temp → arr"]
    direction LR
    A3["5"] --- B3["6"] --- C3["7"] --- D3["8"] --- E3["1"] --- F3["2"] --- G3["3"] --- H3["4"]
  end
  ORIG -->|"pass 1: fill temp"| TEMP
  TEMP -->|"pass 2: copy back"| COPY

Brute-force rotation using a temporary array — two passes, O(n) extra space.

def k_rotate(arr: List[int], k: int) -> None:
    n = len(arr)

    # Normalize k to avoid unnecessary rotations
    k = k % n

    # Create a temporary array of the same size
    temp = [0] * n

    # Copy items into the temp array starting from index k
    for i in range(n):
        # Rotate if we go out of bounds
        temp[i] = arr[(i + k) % n]

    # Copy items from the temp array back to the original array
    for i in range(n):
        arr[i] = temp[i]

arr = [1, 2, 3, 4, 5, 6, 7, 8],  n = 8,  k = 4 % 8 = 4

Pass 1 — temp[i] = arr[(i + k) % n]:
  i=0: temp[0] = arr[(0+4)%8] = arr[4] = 5
  i=1: temp[1] = arr[(1+4)%8] = arr[5] = 6
  i=2: temp[2] = arr[(2+4)%8] = arr[6] = 7
  i=3: temp[3] = arr[(3+4)%8] = arr[7] = 8
  i=4: temp[4] = arr[(4+4)%8] = arr[0] = 1  ← wrap-around kicks in here
  i=5: temp[5] = arr[(5+4)%8] = arr[1] = 2
  i=6: temp[6] = arr[(6+4)%8] = arr[2] = 3
  i=7: temp[7] = arr[(7+4)%8] = arr[3] = 4

temp = [5, 6, 7, 8, 1, 2, 3, 4]

Pass 2 — copy temp → arr:
arr  = [5, 6, 7, 8, 1, 2, 3, 4] ✓

Note: The % operator is what handles the wrap-around.
      Without it, indices 4–7 would go out of bounds.

Applying the Diagnostic Questions

Q1 — Why “rotation = 3 in-place reversals”?

At first glance, rotating an array seems like it must involve moving elements around — shift the first element to the end, shift the second… that’s O(n·k) moves. Or use a temp array and copy. But there’s a beautiful shortcut.

The insight: A left rotation by k positions is mathematically equivalent to three in-place reversals of specific segments.

Here’s the WHY step by step:

• After a left rotation by k, the first k elements move to the end, and the last n-k elements move to the front.
• Think of the array as two halves: [LEFT | RIGHT] where LEFT = first k elements, RIGHT = last n-k elements.
• The goal is to produce [RIGHT | LEFT] — swap those two halves.
• How do 3 reversals achieve this?
  1. Reverse LEFT → its internal order flips: [LEFT_reversed | RIGHT]
  2. Reverse RIGHT → its internal order flips: [LEFT_reversed | RIGHT_reversed]
  3. Reverse the entire array → everything flips, which un-reverses both halves back to their original relative order while swapping their positions: [RIGHT | LEFT] ✓

Concrete check with [1, 2, 3, 4 | 5, 6, 7, 8], k=4:

• Step 1 (reverse LEFT): [4, 3, 2, 1 | 5, 6, 7, 8]
• Step 2 (reverse RIGHT): [4, 3, 2, 1 | 8, 7, 6, 5]
• Step 3 (reverse all): [5, 6, 7, 8, 1, 2, 3, 4] ✓

What breaks if you skip a step? If you only reversed the entire array without the two segment reversals first, you’d get [8, 7, 6, 5, 4, 3, 2, 1] — reversed, not rotated. The two prep reversals are what ensure each half’s internal order is preserved after the final full reversal.

This is the subproblem decomposition: one complex O(n) operation (rotation) → three simpler O(n) operations (reversals), each solvable independently.

Q2 — Why “in-place reversal is the two-pointer flip”?

Reversing a subarray is the canonical two-pointer direct application you already know:

• Place left at the start of the segment, right at the end.
• Swap arr[left] and arr[right], then move left inward and right inward.
• Repeat until they meet in the middle.

Why two pointers? Because the reversal problem has a natural symmetric structure — the element at position i from the left goes to position i from the right. Two pointers exploit that symmetry directly: one pointer tracks “the element that needs to go right” and the other tracks “the element that needs to go left.” They meet in the middle when all swaps are done.

What if you didn’t use two pointers? You’d need an extra array to copy the reversed segment into, then copy it back — that’s O(n) space per reversal, and we’d be back to the brute-force approach. Two pointers make it O(1) space per reversal.

So the full chain of reasoning is:

Rotation → 3 reversals → each reversal → two-pointer → O(1) space total

Critical observation: a left rotation by k is equivalent to three reversal operations:

1. Reverse the first k elements: arr[0..k-1]
2. Reverse the remaining n-k elements: arr[k..n-1]
3. Reverse the entire array: arr[0..n-1]

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  subgraph S0["Original:  [1, 2, 3, 4 | 5, 6, 7, 8]"]
    direction LR
    O1["1"] --- O2["2"] --- O3["3"] --- O4["4"] --- O5["5"] --- O6["6"] --- O7["7"] --- O8["8"]
  end
  subgraph S1["Step 1: Reverse first k=4  →  [4, 3, 2, 1 | 5, 6, 7, 8]"]
    direction LR
    P1["4"] --- P2["3"] --- P3["2"] --- P4["1"] --- P5["5"] --- P6["6"] --- P7["7"] --- P8["8"]
  end
  subgraph S2["Step 2: Reverse last n-k=4  →  [4, 3, 2, 1 | 8, 7, 6, 5]"]
    direction LR
    Q1["4"] --- Q2["3"] --- Q3["2"] --- Q4["1"] --- Q5["8"] --- Q6["7"] --- Q7["6"] --- Q8["5"]
  end
  subgraph S3["Step 3: Reverse entire array  →  [5, 6, 7, 8, 1, 2, 3, 4]"]
    direction LR
    R1["5"] --- R2["6"] --- R3["7"] --- R4["8"] --- R5["1"] --- R6["2"] --- R7["3"] --- R8["4"]
  end

  S0 -->|"reverse arr[0..3]"| S1
  S1 -->|"reverse arr[4..7]"| S2
  S2 -->|"reverse arr[0..7]"| S3

Shift k=4 elements to the left by combining three in-place reversal subproblems — each reversal is solved with the two-pointer technique, O(1) space total.

Each reversal is a direct two-pointer application (left++, right--, swap until they meet). Three subproblems, each O(n), solved in-place with O(1) extra memory.

Two-Pointer Solution

from typing import List

class Solution:
    def reverse(self, arr: List[int], start: int, end: int) -> None:
        # Two-pointer in-place reversal:
        # 'start' moves right, 'end' moves left — they swap and converge
        while start < end:
            arr[start], arr[end] = arr[end], arr[start]  # Swap the two elements
            start += 1  # Shrink window from the left
            end   -= 1  # Shrink window from the right
        # When start >= end, every pair has been swapped — segment is reversed

    def k_rotations(self, arr: List[int], k: int) -> None:
        n = len(arr)

        # Normalize k: rotating n times returns the array unchanged,
        # so k=9 on a length-8 array is the same as k=1
        k %= n

        # Decompose rotation into 3 targeted reversals (the subproblem strategy):
        self.reverse(arr, 0, k - 1)   # Step 1: Reverse the LEFT segment  [0 .. k-1]
        self.reverse(arr, k, n - 1)   # Step 2: Reverse the RIGHT segment  [k .. n-1]
        self.reverse(arr, 0, n - 1)   # Step 3: Reverse entire array — un-reverses both halves
                                      #          and places RIGHT before LEFT, achieving the rotation


arr = [1, 2, 3, 4, 5, 6, 7, 8]
Solution().k_rotations(arr, 4)
print(arr)   # Expected: [5, 6, 7, 8, 1, 2, 3, 4]

arr = [1, 2, 3, 4, 5, 6, 7, 8],  n = 8,  k = 4 % 8 = 4

━━━ reverse(arr, 0, 3) — flip LEFT segment [0..3] ━━━
  start=0 (1), end=3 (4) │ 0 < 3 → swap │ [4, 2, 3, 1, 5, 6, 7, 8] │ start=1, end=2
  start=1 (2), end=2 (3) │ 1 < 2 → swap │ [4, 3, 2, 1, 5, 6, 7, 8] │ start=2, end=1
  start=2,     end=1     │ 2 > 1 → done

After step 1: [4, 3, 2, 1, 5, 6, 7, 8]

━━━ reverse(arr, 4, 7) — flip RIGHT segment [4..7] ━━━
  start=4 (5), end=7 (8) │ 4 < 7 → swap │ [4, 3, 2, 1, 8, 6, 7, 5] │ start=5, end=6
  start=5 (6), end=6 (7) │ 5 < 6 → swap │ [4, 3, 2, 1, 8, 7, 6, 5] │ start=6, end=5
  start=6,     end=5     │ 6 > 5 → done

After step 2: [4, 3, 2, 1, 8, 7, 6, 5]

━━━ reverse(arr, 0, 7) — flip ENTIRE array [0..7] ━━━
  start=0 (4), end=7 (5) │ 0 < 7 → swap │ [5, 3, 2, 1, 8, 7, 6, 4] │ start=1, end=6
  start=1 (3), end=6 (6) │ 1 < 6 → swap │ [5, 6, 2, 1, 8, 7, 3, 4] │ start=2, end=5
  start=2 (2), end=5 (7) │ 2 < 5 → swap │ [5, 6, 7, 1, 8, 2, 3, 4] │ start=3, end=4
  start=3 (1), end=4 (8) │ 3 < 4 → swap │ [5, 6, 7, 8, 1, 2, 3, 4] │ start=4, end=3
  start=4,     end=3     │ 4 > 3 → done

After step 3: [5, 6, 7, 8, 1, 2, 3, 4] ✓

Total swaps: 2 + 2 + 4 = 8  (all within O(n))
Extra space:  0 — every swap is in-place

Problems in This Category

Difficulty increases as the nesting depth grows — Four Sum has three nested loops where the innermost is two-pointer.