DSA sheet · Arrays · Two Pointers pattern

3Sum

The second two-pointer problem, right after Two Sum II. Now we need three numbers that add to 0, and we must return every such triplet, without repeats. The teacher first writes the obvious three nested loops (O(n³)) and shows from the constraints that it's far too slow. Then she turns three pointers into "one fixed pointer + the Two Sum II two pointers" after sorting the array. Her first version works but returns duplicate triplets, so she shows exactly where the duplicates come from and adds the skipping rules one by one.

Why it matters: "fix one element, then two pointers on the rest" turns a k-sum into a (k−1)-sum, and the duplicate-skipping rules here are reused in 4Sum and many "unique combinations" problems.

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 (pairs, opposite ends, fixing one element, duplicates)
• Part A · Brute force: three nested loops
• Part B · Sort, fix i, two pointers on the rest (first version, still has duplicates)
• Part C · Skipping duplicates (the final solution)
• Part D · Revision page

Part 0 · Before starting

What is a "pointer"?

A pointer here is just a variable holding an index of the array. "Moving" it means adding or subtracting 1. Two-pointer solutions keep a few such indexes and move them by rules, instead of using nested loops that try every combination.

The brute force over all pairs, and why sorting lets us skip pairs

For "find two numbers with sum X", trying every pair costs about n²/2 checks. If the array is sorted, we can do it in one pass: left at the start, right at the end.

• Sum too big → right -= 1. Every partner of right that's still in range is ≥ nums[left], so every pair using right is at least as big as the current sum, i.e. also too big. right is useless; drop it.
• Sum too small → left += 1. Every partner of left is ≤ nums[right], so every pair using left is also too small. Drop it.
• Sum equal → found a pair.

Each move throws away a whole row of pairs that we've proven can't work. That's why the scan is safe and why it's O(n). This is the opposite-end shape, from Two Sum II (Problem 1).

Fixing one element: from 3 numbers to 2

3Sum asks for three numbers a + b + c = 0. If we fix a (with a normal loop), then we need b + c = −a. That's exactly "find a pair with a given sum" in the part of the array after a, so we can run the opposite-end two pointers there. One loop × one O(n) scan = O(n²) instead of O(n³).

Skipping duplicates, the idea

After sorting, equal values sit next to each other. So "have I already used this value in this position?" becomes a simple check: "is this the same as its neighbour?" If yes, skip it. Part C shows exactly where.

The other two-pointer shapes on this sheet

Not needed for 3Sum, but good to recognise.

The teacher's 4 array patterns

Part A · Brute force: three nested loops

LeetCode 15

1The question in simple words

You get an integer array nums. Return all triplets [nums[i], nums[j], nums[k]] such that:

• i, j, k are three different indexes (i ≠ j, j ≠ k, i ≠ k), and
• nums[i] + nums[j] + nums[k] = 0.

The answer must not contain duplicate triplets. Two triplets are duplicates if they have the same three values, in any order. For example [−1, 0, 1] and [0, −1, 1] are the same triplet: written in sorted order, both are [−1, 0, 1]. Keep one.

Note: [−1, 0, 1] can be made with the −1 at index 0 or the −1 at index 4. Different indexes, same values → still only one triplet in the answer. The order of the triplets in the output doesn't matter.

2What the constraints tell us

• 3 ≤ n ≤ 3000 (3·10³). O(n²) ≈ 9·10⁶ → fine. O(n³) ≈ 2.7·10¹⁰ (the teacher says 27·10⁹) → way past ~10⁸, TLE. So we need to get to O(n²).
• −10⁵ ≤ nums[i] ≤ 10⁵. A normal int holds about ±2·10⁹. The biggest sum of three values is 3·10⁵, so an int is fine. (Python ints never overflow anyway.)
• n ≥ 3 → there's always at least one triplet to look at. The answer can still be empty (e.g. [0, 1, 1]).

3Intuition: try every group of three

Three fingers: i, j, k, always in order i < j < k. Start them at 0, 1, 2. Move k to the end, checking every sum. Then move j one step and run k again from just after j. When j runs out, move i. This visits every group of three cells exactly once.

4Building the logic

Her first draft, and the fix

She first writes all three loops starting from 0, then corrects it: each loop must start one after the previous pointer, so that the indexes are different and no group is checked twice.

• k starts at j + 1, j starts at i + 1.
• Then the end points: k runs to the last index (n − 1). For k to have room, j must stop at the second-last index (j < n − 1). For j to have room, i must stop at the third-last (i < n − 2).

Inside: if nums[i] + nums[j] + nums[k] == 0, save the triplet.

5Approach steps

1. Sort nums.
2. For every i < j < k: if the three values add to 0, add the tuple to a set.
3. Return the set as a list of lists.

6Code (Python)

class Solution:
    def threeSum(self, nums):
        nums.sort()                          # so every triplet comes out in sorted order
        n = len(nums)
        found = set()                        # a set keeps one copy of each triplet
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j + 1, n):
                    if nums[i] + nums[j] + nums[k] == 0:
                        found.add((nums[i], nums[j], nums[k]))
        return [list(t) for t in found]

7Code line by line

8Dry run (hand table)

nums = [−1, 0, 1, 2, −1, −4] → sorted [−4, −1, −1, 0, 1, 2]. Only the groups that add to 0 are shown (there are 20 groups in total).

Answer: [[−1, −1, 2], [−1, 0, 1]] ✓. Without the set, [−1, 0, 1] would appear twice.

9Complexity & remember

• Time O(n³): three nested loops. For every i, j runs; for every j, k runs. For n = 3000 that's about 2.7·10¹⁰ steps → TLE.
• Space O(number of triplets) for the set.

Part B · Sort, fix i, two pointers on the rest

first version: fast, but it still returns duplicates

1The question again, with the new goal

Same question. Goal: O(n²). Idea: keep the outer i loop, but replace the two inner loops (j and k) with one two-pointer scan.

2Choosing the pattern (her reasoning)

• Sliding window, prefix sum, Kadane's all need a continuous part of the array. Our three numbers can be anywhere → all three fail.
• That leaves two pointers. But we need three positions, not two. Her answer: one pointer (i) keeps moving in a for loop as before; the other two (j and k) are handled together by a while loop, exactly like Two Sum II.
• Two pointers needs a sorted array → sort first. We're allowed to, because the answer is values, not indexes.

3Intuition: Two Sum II inside a loop

Fix nums[i]. Now we need two numbers after it that add to −nums[i]. Put j (we'll call it left) right after i, and k (right) at the last index. Compute the total of all three:

• total == 0 → save the triplet.
• total > 0 → too big → right -= 1 (a smaller number).
• total < 0 → too small → left += 1 (a bigger number).

Stop when left meets right. Then the for loop moves i forward and we do it again.

4Building the logic from examples

The teacher builds her own sorted array: three −1s, three 0s, one 1, two 2s and a 3.

Too big → move right

−1 + (−1) + 3 = 1, but we want 0. It's too big, so we need to add a smaller number. Would moving left forward give something smaller? No: moving forward in a sorted array gives bigger-or-equal values. Moving right back gives smaller-or-equal values. So right -= 1.

Too small → move left

If the total is negative, we need a bigger number, so left += 1.

Never touch i inside the while

The teacher stresses this: inside the scan we only play with left and right. i moves only through the for loop.

Why sorting makes these moves safe (the full reason)

Fix i. The pairs still "alive" are all (l, r) with left ≤ l < r ≤ right. Suppose the total is too big: nums[i] + nums[left] + nums[right] > 0. Take any alive pair that uses right: its other index l is ≥ left, so nums[l] ≥ nums[left] (sorted). Then:

nums[i] + nums[l] + nums[right] ≥ nums[i] + nums[left] + nums[right] > 0

So every remaining triplet that uses right is too big. None of them can be an answer. Dropping right loses nothing. The "too small" case is the mirror: every remaining partner of left is ≤ nums[right], so every triplet using left is too small, and dropping left loses nothing.

Without sorting, none of this holds: moving right back could give a bigger number, and we'd have no idea which pointer to move.

The bug: duplicates appear

Run this first version on her array and watch i:

• i = 0 (−1) finds [−1, −1, 2] (indexes 0, 1, 8). Then left and right move one step: (0, 2, 7) is again −1, −1, 2 → duplicate. Then [−1, 0, 1].
• i = 1 is also −1. Everything it can find, i = 0 already found: [−1, −1, 2] and [−1, 0, 1] again → duplicates.
• i = 2, another −1 → [−1, 0, 1] a third time.

In total this version returns 7 triplets, but only 3 are different. Part C fixes it.

5Approach steps

1. Sort nums. Let n = len(nums).
2. For i from 0 to n − 3: left = i + 1, right = n − 1.
3. While left < right: total = nums[i] + nums[left] + nums[right].
4. total == 0 → save, then move both pointers. total > 0 → right −= 1. total < 0 → left += 1.

6Code (Python)

class Solution:
    def threeSum(self, nums):
        nums.sort()
        n = len(nums)
        result = []
        for i in range(n - 2):               # leave room for left and right
            left, right = i + 1, n - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total == 0:
                    result.append([nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1
                elif total > 0:
                    right -= 1               # too big: take a smaller number
                else:
                    left += 1                # too small: take a bigger number
        return result

7Code line by line

8Dry run: where the duplicates come from

Her array [−1, −1, −1, 0, 0, 0, 1, 2, 2, 3]. Only the found triplets are listed.

Two sources of repeats: i landing on a value it already used (rows 4–6), and left/right stepping onto a copy of the value they just used (row 2).

9Complexity & remember

• Time O(n²): sorting is O(n log n). The for loop runs about n times, and each while scan is O(n) because left and right only move toward each other. n · n = n² dominates.
• Space O(1) extra, apart from the output (and the memory Python's sort uses internally).

Part C · Skipping duplicates (the final solution)

LeetCode 15 · the code she submits

1What stays the same, what changes

Same question, same constraints, same sort + fix i + two pointers. We only add two things: a skip for i, and a skip for left and right right after a triplet is found.

2Why not just use a set?

The teacher mentions it: you could store triplets in a set and duplicates would vanish. It works, but it still does the repeated work (finding the same triplet again and again), and the set costs extra memory. Skipping is better: we never even produce a duplicate.

3Intuition: once a value is used in a position, don't use it there again

Because the array is sorted, all copies of a value are neighbours. So:

• If i lands on the same value as the previous i, every triplet it could find was already found. Skip it.
• After saving a triplet, if left would step onto the same value again (or right would), we'd just rebuild the same triplet. Walk past all the copies.

4Building each skip, exactly where it goes

Skip 1: at the top of the for loop, for i

Her explanation: with the first −1 as i, left and right already found every triplet that starts with −1. If the next i is also −1, it can only find the same triplets again (its left/right range is even smaller). So:

On her array: i = 0 is −1 → used. i = 1 is −1, same as nums[0] → skip. i = 2 is −1 → skip. i = 3 is 0, different from nums[2] → use it.

Skip 2: inside if total == 0, for left and right

On her array, i = 0, the triplet [−1, −1, 2] is at left = 1, right = 8. If we just did left += 1, right −= 1, we'd land on another −1 and another 2 and save the same triplet again. So after saving, walk left forward while the next value is the same, and walk right back while the previous value is the same:

while left < right and nums[left] == nums[left + 1]:
    left += 1        # walk to the LAST copy of this left value
while left < right and nums[right] == nums[right - 1]:
    right -= 1       # walk to the FIRST copy of this right value
left += 1            # one more step: off the copies, onto a new value
right -= 1

Her walk-through: left is on the −1 at index 1. Is nums[2] also −1? Yes → move left to 2. Is nums[3] also −1? No, it's 0 → stop. Left now sits on the last −1, so one more left += 1 puts it on the 0. Right is on the 2 at index 8. Is nums[7] also 2? Yes → move right to 7. Is nums[6] 2? No, it's 1 → stop, and one more right -= 1 puts it on the 1.

5Approach steps

1. Sort nums, result = [].
2. For i in 0 … n − 3: if i > 0 and nums[i] == nums[i − 1] → continue (Skip 1).
3. left = i + 1, right = n − 1. While left < right: compute total.
4. total == 0: save; skip left copies; skip right copies; left += 1; right −= 1 (Skip 2).
5. total > 0: right −= 1. total < 0: left += 1.
6. Return result.

6Code (Python)

class Solution:
    def threeSum(self, nums):
        nums.sort()
        n = len(nums)
        result = []
        for i in range(n - 2):
            if i > 0 and nums[i] == nums[i - 1]:    # Skip 1: same fixed value as last time
                continue
            left, right = i + 1, n - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total == 0:
                    result.append([nums[i], nums[left], nums[right]])
                    # Skip 2: walk past copies of the values we just used
                    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 total > 0:
                    right -= 1
                else:
                    left += 1
        return result

7Code line by line (only the new lines)

8Dry run

Her array [−1, −1, −1, 0, 0, 0, 1, 2, 2, 3] (indexes 0–9).

Final answer: [[−1, −1, 2], [−1, 0, 1], [0, 0, 0]] ✓, three triplets and no repeats (Part B gave 7).

The array at the key moments. Yellow = the three pointer cells, grey = cells already ruled out for this i.

LeetCode's example [−1, 0, 1, 2, −1, −4] sorts to [−4, −1, −1, 0, 1, 2]. i = 0 (−4): totals −3, −3, −2, −1 → left moves every time, nothing found. i = 1 (−1): finds [−1, −1, 2], then [−1, 0, 1]. i = 2 (−1): Skip 1. i = 3 (0): 0 + 1 + 2 = 3 → no. Answer [[−1, −1, 2], [−1, 0, 1]] ✓.

9Complexity & remember

• Time O(n²). Sorting is O(n log n). For each i, left and right together move at most n steps (the skip loops are still left/right moves, so they don't add extra rounds). n values of i × O(n) = O(n²). For n = 3000 that's about 9·10⁶, fast.
• Space O(1) extra besides the output (Python's sort uses some memory internally). No set needed.

She submitted the code (Java on screen, with Python and C++ versions of the same logic shown after) and it passed.

Part D · Revision page

s = Solution()
print(s.threeSum([-1, 0, 1, 2, -1, -4]))            # [[-1, -1, 2], [-1, 0, 1]]
print(s.threeSum([-1, -1, -1, 0, 0, 0, 1, 2, 2, 3])) # [[-1, -1, 2], [-1, 0, 1], [0, 0, 0]]
print(s.threeSum([0, 1, 1]))                         # []
print(s.threeSum([0, 0, 0, 0]))                      # [[0, 0, 0]]
print(s.threeSum([-2, 0, 1, 1, 2]))                  # [[-2, 0, 2], [-2, 1, 1]]

Based on this video: 3Sum | Two Pointers