DSA sheet · Arrays · Two Pointers pattern

Two Pointers Introduction

This video opens the pattern-wise sheet. The array section has four patterns: two pointers, sliding window, prefix sum and Kadane's algorithm. Two pointers comes first. The teacher doesn't just say "use two pointers". She takes the first problem, Two Sum II, and checks each of the four patterns against it, crossing out the ones that don't fit. Then she writes the brute force (two nested loops, O(n²)), shows from the constraints that it's too slow, and uses the fact that the array is sorted to get an O(n) solution with one pointer at each end.

Why it matters: "sorted array + find a pair" is the most common place two pointers shows up, and the reason it works (each move throws away pairs that can't be the answer) is the same reason it works in 3Sum, Container With Most Water and many others.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Two pointers from scratch (the idea, the 4 array patterns, the shapes you'll meet)
• Part A · Two Sum II, brute force: try every pair
• Part B · Two Sum II, optimal: one pointer at each end
• Part C · Revision page

Part 0 · Before starting

What is a "pointer" here?

In these problems a pointer is just a variable that holds an index of the array (0, 1, 2, …). It "points" at one cell. When we say "move the pointer", we mean add 1 to it or subtract 1 from it. "Two pointers" means we keep two such index variables at once and move them by some rule, instead of using two nested loops.

The brute force over all pairs, and why it's slow

If a question asks about two elements (a pair), the simple way is to try every pair: an outer loop picks the first index i, an inner loop picks the second index j after it. With n elements that is n·(n−1)/2 pairs, which grows like n². For n = 30,000 that's about 4.5·10⁸ pairs, already past the rough limit of ~10⁸ simple steps per second that a judge allows.

Two pointers is a way of not looking at most of those pairs, while still being sure the answer isn't among the ones we skip. To skip pairs safely we need some extra information about the array. Usually that's the fact that it's sorted (or that we're allowed to sort it). Sorted means each step left gives a smaller-or-equal number, and each step right gives a bigger-or-equal number. That one fact lets us say "every pair using this element is too big" without checking them one by one.

The teacher's 4 array patterns, and how she rules them out

Her habit: before coding, go through the four patterns and ask "does this one fit?" For Two Sum II she does it like this:

Shape 1: opposite-end pointers (this video)

left starts at index 0, right starts at index n − 1. Each step looks at the two values, then moves one of them inward. They stop when they meet. On a sorted array:

• Moving left one step right gives a bigger or equal value, so the pair sum goes up (or stays).
• Moving right one step left gives a smaller or equal value, so the pair sum goes down (or stays).

So we have a "make it bigger" button and a "make it smaller" button. If the sum is too big, press "smaller"; if too small, press "bigger". Part B explains carefully why pressing a button never throws away the answer.

The other shapes you'll meet later on this sheet

Not covered in this video. They're here so you can recognise them when they come.

Why read constraints first?

The teacher reads the constraints before thinking of any approach. They tell us (1) whether a brute force will be fast enough (more than about 10⁸ steps → TLE, "Time Limit Exceeded"), (2) whether values fit in a normal int, and (3) which edge cases exist (can the array be empty? can there be no answer?).

Part A · Two Sum II, brute force: try every pair

LeetCode 167 · Two Sum II – Input Array Is Sorted

1The question in simple words

You get an array numbers that is already sorted in non-decreasing order (each number is ≥ the one before it; equal neighbours are allowed, so "ascending, with possible repeats"). You also get a target. Find the two numbers that add up to target and return their positions.

• There is exactly one answer, so we don't have to worry about choosing between several.
• You may not use the same element twice: the two positions must be different (but two different cells may hold the same value).
• Positions are 1-indexed: the first cell is position 1, not 0. So we return [index1 + 1, index2 + 1].

2What the constraints tell us

• 2 ≤ n ≤ 3·10⁴. At least two numbers, so a pair always exists to look at. An O(n²) approach is about (3·10⁴)² = 9·10⁸ steps → the teacher says this will give TLE. We'll need something faster.
• −1000 ≤ numbers[i] ≤ 1000, and target in the same range. Small values; any sum of two fits in an int easily. Negatives are allowed (that's what made her pause on Kadane's).
• Sorted in non-decreasing order. This is the key line. The teacher's rule: any fact the question gives you is there for a reason, and usually it's the hint for the optimisation.
• Exactly one solution. We can return as soon as we find it.

3Intuition: check every pair

Forget patterns for a moment. Point one finger i at a number, and with another finger j try every number after it. If the two add to target, we're done. If not, move j. When j runs out, move i one step and start j again just after it.

4Building the logic

Why j starts at i + 1

We can't use the same element twice, so j must never equal i. Also, pairs before i were already tried when the outer loop was at those earlier positions (pair (0, 2) is the same pair as (2, 0)). So j starts one after i.

Why i stops at the second-last index

i runs while i < n − 1, so its last value is n − 2. If i went all the way to n − 1 (the last cell), then j = i + 1 = n would be past the end, and there's no partner left anyway. Stopping one early keeps j inside the array.

The check

For each pair: if numbers[i] + numbers[j] == target, return the positions. Remember the 1-indexing: return [i + 1, j + 1]. The question promises one answer exists, but if we finish both loops without finding it, we return [-1, -1] as a "not found" signal (the teacher does this so every path of the function returns something).

5Approach steps

1. For i from 0 to n − 2:
2. For j from i + 1 to n − 1:
3. If numbers[i] + numbers[j] == target → return [i + 1, j + 1].
4. After both loops → return [-1, -1].

6Code (Python)

class Solution:
    def twoSum(self, numbers, target):
        n = len(numbers)
        for i in range(n - 1):              # first number: up to the second-last
            for j in range(i + 1, n):       # second number: always after i
                if numbers[i] + numbers[j] == target:
                    return [i + 1, j + 1]   # the question counts from 1
        return [-1, -1]                     # not found (won't happen here)

7Code line by line

8Dry run (hand table)

numbers = [2, 7, 11, 15], target = 9.

Lucky: the very first pair works. Now a case where it doesn't: target = 26 (11 + 15).

Notice: when i = 0, j moves 1, 2, 3. When i = 1, j moves 2, 3. When i = 2, j moves 3. That's the "for every i, j runs again" pattern that makes it n².

9Complexity & remember

• Time O(n²). The teacher counts it as about (n − 1) for the outer loop times about (n − 1) for the inner loop, because the loops are nested: for each value of i, j runs again. Multiplying gives n² minus smaller terms, and in big-O we keep only the biggest term → n². (The exact count is n·(n−1)/2 pairs, since j only runs over what's after i. Halving doesn't change the big-O.) For n = 3·10⁴ that's far too many → TLE.
• Space O(1): just two index variables.

Part B · Two Sum II, optimal: one pointer at each end

LeetCode 167

1The question again, with the new goal

Same question. Now we want O(n) time, and we'll get it by using the fact that the array is sorted.

2What the constraints tell us now

• n up to 3·10⁴ → O(n) is 3·10⁴ steps, tiny.
• Sorted → two pointers fit. The teacher's words, roughly: when the array is sorted you can apply two pointers without hesitation.
• "Same element not twice" → the pointers must never be on the same cell, which decides the loop condition (left < right, not <=).

3Intuition: two buttons, "bigger" and "smaller"

Put left on the smallest number (index 0) and right on the biggest (index n − 1). Add them.

• Sum equals target → found it.
• Sum is too big → we need a smaller total. The bigger of the two numbers is at right, so swap it for the next smaller one: right -= 1.
• Sum is too small → we need a bigger total. Swap the smaller number for the next bigger one: left += 1.

Each step moves exactly one pointer one cell inward, so after at most n − 1 steps they meet.

4Building the logic from the example

Her example: [2, 7, 11, 15], target 9

left on 2, right on 15: 2 + 15 = 17. That's bigger than 9. We want a smaller total. Of 2 and 15, the larger one is 15, so replace 15 with the number just below it: move right to 11.

2 + 11 = 13, still bigger than 9. The teacher asks: should we now move left to 7 instead? That would give 7 + 11 = 18, which goes the wrong way (bigger, not smaller). So no: when the sum is too big, it's always right that moves. Move right to 7.

2 + 7 = 9 = target. Return positions [1, 2].

Why moving a pointer can never skip the answer

This is the heart of the pattern, so let's be careful. At any moment, all the pairs still "alive" are the ones with both indexes between left and right.

• Sum too big (numbers[left] + numbers[right] > target). Look at every alive pair that uses right: its partner is some index k with left ≤ k < right. Because the array is sorted, numbers[k] ≥ numbers[left]. So numbers[k] + numbers[right] ≥ numbers[left] + numbers[right] > target. Every pair using right is too big, even with the smallest partner available. So right can't be in the answer, and we can safely drop it: right -= 1.
• Sum too small. Every alive pair using left has a partner k with left < k ≤ right, so numbers[k] ≤ numbers[right], and the sum is ≤ the current sum < target. Every pair using left is too small, even with the biggest partner. Drop it: left += 1.

So each move throws away a whole row of pairs at once, and we've just proven none of them was the answer. That's how n² pairs become n steps.

Why while left < right and not left <= right

The teacher's example: the array has a single 5 and target is 10. If the loop allowed left == right, both pointers could sit on that one 5, add it to itself, get 10, and report a "pair". But that's the same element used twice, which isn't allowed. With left < right, the loop stops the moment they meet, so they're always two different cells.

The 1-indexed answer

The teacher noticed from Example 1 that for 2 and 7 (at indexes 0 and 1) the expected output is [1, 2]. So we return [left + 1, right + 1].

What if the array weren't sorted?

Her closing tip:

• If it's not sorted but we're allowed to sort it (and the constraints allow the O(n log n) cost of sorting), sort first, then use two pointers.
• If we're not allowed to sort (for example, the question wants the original positions, as in the first "Two Sum" problem), use a hash map instead: for each number, check if target − number was seen before.

5Approach steps

1. left = 0, right = n − 1.
2. While left < right: total = numbers[left] + numbers[right].
3. If total == target → return [left + 1, right + 1].
4. If total > target → right -= 1 (need smaller).
5. Else → left += 1 (need bigger).
6. After the loop → return [-1, -1].

6Code (Python)

class Solution:
    def twoSum(self, numbers, target):
        left = 0
        right = len(numbers) - 1
        while left < right:                     # never the same cell
            total = numbers[left] + numbers[right]
            if total == target:
                return [left + 1, right + 1]     # 1-indexed answer
            elif total > target:
                right -= 1                       # too big: take a smaller number
            else:
                left += 1                        # too small: take a bigger number
        return [-1, -1]                          # not found

7Code line by line

8Dry run

numbers = [2, 7, 11, 15], target = 9.

A second run where left has to move: numbers = [−3, 1, 4, 6, 9], target = 7.

9Complexity & remember

• Time O(n). The teacher's reasoning: every index is touched by one pointer only. Once left has passed a cell, right will never visit it, because the loop ends when they meet. Each step moves one pointer one cell, so there are at most n − 1 steps, and each step is O(1) work (one addition, one comparison).
• Space O(1): two indexes and a sum. (LeetCode actually requires constant extra space for this problem, which also rules out the hash-map idea.)

She submitted it and it beat about 96% of solutions.

Part C · Revision page

s = Solution()
print(s.twoSum([2, 7, 11, 15], 9))      # [1, 2]
print(s.twoSum([2, 3, 4], 6))           # [1, 3]
print(s.twoSum([-1, 0], -1))            # [1, 2]
print(s.twoSum([1, 5, 5, 8], 10))       # [2, 3]  (two different 5s)
print(s.twoSum([-3, 1, 4, 6, 9], 7))    # [2, 4]

Based on this video: Two Pointers Introduction | Two Sum II