Edit Problem

Title

Problem URL

Difficulty

Tags

Two Pointers

Go file path (optional)

Notes (optional)

## What It Does

Finds all unique triplets in an array that sum to zero. It sorts the array first, then for each element treats it as the "anchor" and runs a two-pointer search on the remaining subarray to find pairs that sum to its negation. Duplicate-skipping logic at both the outer and inner loops ensures no repeated triplets in the output.

For example, `[-3, 0, 1, 2, -1, 1, -1]` → `[[-3, 1, 2], [-1, 0, 1], [-1, -1, 2]]`.

---

## Complexity Analysis

**Time Complexity: O(n²)**

Sorting is O(n log n), but the dominant cost is the nested loop. The outer loop runs O(n) times, and for each iteration the two-pointer inner loop runs O(n) — giving O(n²) overall. The duplicate-skipping steps don't change this since they're still bounded by the inner loop's range.

**Space Complexity: O(n)**

Excluding the output, `sort.Ints` uses O(log n) stack space for its internal quicksort. The output slice `triplets` can grow up to O(n²) in the worst case (e.g. an array of all zeros), so if you count the output it's O(n²).

---

## Things to Be Careful/Mindful Of

**The duplicate-skip after a match has an off-by-one risk.** After finding a valid triplet, you advance `left` and `right`, then skip further duplicates. The inner skip checks `arr[left] == arr[left-1]` — this is safe *only because* you already incremented `left`. If the order were swapped (skip before increment), you'd be comparing against the element you just used and could skip valid values.

**The `sum > target_sum` / `sum < target_sum` branches should be `else if`.** Right now, after a match is found and `left`/`right` are moved, the code falls through into both `if` checks. This means on a match iteration, you're moving the pointers an *extra* time unnecessarily. It works correctly by accident (the extra moves are usually harmless), but it's a logic bug waiting to cause subtle issues. They should be `else if` or combined with the match as an `if / else if / else` chain.

**The outer loop bound `len(arr) - 2` is intentional but easy to second-guess.** You need at least 3 elements ahead for a valid triplet, so stopping 2 early is correct. Worth a comment since it looks like an off-by-one at first glance.

**Sorting mutates the input array.** `sort.Ints` sorts in place, so the caller's original slice ordering is destroyed. If the caller needs the original order preserved, you'd need to sort a copy instead.

First solved

Mar 3, 2026