Topic: Learning notes

LeetCode 15: 3Sum in TypeScript, Why Skipping Duplicates Does Not Lose Answers

My progression from a global Set that loses answers to two pointers, with an explanation of all three duplicate checks, complexity, and executable assertions.

I first used three nested loops and a Set of used indices. After switching to sorting and two pointers, the search worked but still returned duplicate answers. AI helped supply the duplicate checks. This note explains them and includes executable checks for revisiting the problem later.

The problem

LeetCode 15: 3Sum asks for every unique triplet whose sum is zero. Each triplet uses three distinct indices and contains values, not indices. Output order does not matter. The input length is 3 to 3000, with values between -100000 and 100000.

For example, [-1, 0, 1, 2, -1, -4] produces [[-1, -1, 2], [-1, 0, 1]].

Why my first version missed answers

After finding an answer, my first version called set.add(i), set.add(j), and set.add(k), then skipped those indices later. That effectively consumed the elements.

But [-1, -1, 2] and [-1, 0, 1] may share an index holding -1. Only indices within a single triplet must differ. A global used-index Set incorrectly removes valid answers.

Starting all three loops at zero also checks different permutations of the same indices. The corrected brute-force reference below uses i < j < k and a sorted triplet as its deduplication key.

function threeSumBruteForce(nums: number[]): number[][] {
    const unique = new Map<string, number[]>();
    for (let i = 0; i < nums.length - 2; i++) {
        for (let j = i + 1; j < nums.length - 1; j++) {
            for (let k = j + 1; k < nums.length; k++) {
                if (nums[i] + nums[j] + nums[k] !== 0) continue;
                const triplet = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);
                unique.set(triplet.join(","), triplet);
            }
        }
    }
    return [...unique.values()];
}

This is an added reference implementation, not my original code. Enumeration takes expected O(n³) time under expected constant-time Map operations. Each sort handles only three values. With m unique answers, the Map and output occupy O(m) space.

My final version with AI-assisted duplicate checks

This preserves my final control flow, with an explicit array type and semicolons added. I wrote the sorting and pointer search after hints; the duplicate checks came from an AI-provided correction.

function threeSum(nums: number[]): number[][] {
    const arr: number[][] = [];
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let left = i + 1;
        let right = nums.length - 1;
        while (right > left) {
            const sum = nums[i] + nums[left] + nums[right];
            if (sum > 0) {
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                arr.push([nums[i], nums[left], nums[right]]);
                right--;
                left++;
                while (left < right && nums[left] === nums[left - 1]) {
                    left++;
                }
                while (left < right && nums[right] === nums[right + 1]) {
                    right--;
                }
            }
        }
    }
    return arr;
}

Fixing nums[i] leaves a two-number target of -nums[i]. In sorted order, move left when the sum is too small and right when it is too large.

If the sum is too small, right is already the largest remaining position. Keeping left and selecting a smaller right value cannot raise the sum to zero, so that left endpoint can be discarded. The argument is symmetric for a sum that is too large. Each move eliminates pairs that cannot work.

The first check: search each fixed value once

if (i > 0 && nums[i] === nums[i - 1]) continue;

For [-1, -1, 0, 1], fixing the first -1 already finds [-1, 0, 1]. Fixing the second -1 gives the same target and a smaller remaining suffix. It cannot introduce a new value combination that the earlier search could not find.

This does not exclude [-1, -1, 2]. When i points to the first -1, left may point to the second. The values match, but their indices differ.

The i > 0 guard means the first value has no predecessor to compare against and must be searched.

The next two checks: skip equal values after recording an answer

Take [-2, 0, 0, 2, 2] with -2 fixed:

After left++, the value just used is at left - 1. Comparing nums[left] === nums[left - 1] checks whether the new value is still the same. Keep advancing through that run of equal values.

After right--, the previous right value is at right + 1. That explains why the left check looks backward and the right check looks forward.

With the first value a and second value b fixed, the third value must be -a - b. Once [a, b, c] has been recorded, another equal b can only produce the same c. It cannot create a new value combination. The same reasoning applies to another equal c.

These checks run after recording the answer. Converting the whole input to a Set would remove the repeated elements needed for [-1, -1, 2] and [0, 0, 0]. The left < right guard keeps the remaining search on two distinct positions.

Completeness and uniqueness

For a fixed i, all candidate pairs not yet eliminated remain between the pointers. Sorted order justifies discarding an endpoint when the sum is too small or too large. On a match, the code records the answer and skips endpoint values that could only reproduce it.

The outer loop searches each first value once. The inner loop records each matching value pair once. The invariant i < left < right guarantees three distinct indices. Together, these properties explain why the result is complete and contains no duplicates.

Complexity and optional cleanup

For each i, the pointers move only inward, so the search is linear. There are at most n outer iterations, giving O(n²) search time. Under the usual O(n log n) sorting assumption, total time remains O(n²).

Pointer state uses O(1) extra space, and m output triplets use O(m). Sorting workspace depends on the engine, so the whole function should not be called constant space. MDN’s sort documentation states that sort complexity is implementation dependent and that it mutates the input.

My i < nums.length bound is correct; the final two iterations never enter while. Using i < nums.length - 2 avoids those empty iterations. An optional early exit at nums[i] > 0 is also safe because no negative values remain. These are added cleanup suggestions, not the reason deduplication works.

Executable verification

Put both functions and these checks in one TypeScript file. Canonicalization changes only ordering, not multiplicity. An extra duplicate result therefore still fails the assertion.

import assert from "node:assert/strict";

function canonical(groups: number[][]): string[] {
    return groups.map(group => [...group].sort((a, b) => a - b).join(",")).sort();
}

const cases: [number[], number[][]][] = [
    [[-1, 0, 1, 2, -1, -4], [[-1, -1, 2], [-1, 0, 1]]],
    [[0, 1, 1], []],
    [[0, 0, 0, 0], [[0, 0, 0]]],
    [[-1, -1, 0, 1], [[-1, 0, 1]]],
    [[-2, 0, 0, 2, 2], [[-2, 0, 2]]],
    [[-1, -1, 2], [[-1, -1, 2]]],
];

for (const [input, expected] of cases) {
    assert.deepEqual(canonical(threeSum([...input])), canonical(expected));
    assert.deepEqual(canonical(threeSumBruteForce(input)), canonical(expected));
}

The [-1, -1, 2] case ensures valid repeated values survive; four zeros test that the same answer is emitted only once. These checks were added for the article.

What to revisit

Before rewriting from a blank file, explain why separate answers may share indices and why an equal first value needs no new search. Then trace [-2, 0, 0, 2, 2] to explain the left - 1 and right + 1 comparisons. Deriving those conditions is the part to practice again.

References

• LeetCode 15: 3Sum
• MDN: Array.prototype.sort()
• Node.js: Strict assertion mode