codejump
MediumPythonJavaScriptTypeScript

Two Pointers — 3Sum

AlgorithmsTwo PointersArraysSorting

Return every unique triplet [a, b, c] of values from nums with
a + b + c === 0. Each triplet uses three different positions, and the same
triplet of values must appear only once, even if the input contains it several
ways.

Sort the array, fix the first value, then find the other two with two pointers
moving towards each other: O(n²) instead of O(n³). Skipping equal neighbours is
what removes the duplicates.

Output order (deterministic)

  • Each triplet is in ascending order.
  • Triplets are sorted lexicographically (by first value, then second).

Examples

solve([-1, 0, 1, 2, -1, -4])  → [[-1, -1, 2], [-1, 0, 1]]
solve([0, 1, 1])              → []
solve([0, 0, 0, 0])           → [[0, 0, 0]]

Constraints

  • 0 <= nums.length <= 3000
  • -100000 <= nums[i] <= 100000

Sample tests

Test #1The classic example
Input: [[-1,0,1,2,-1,-4]]
Output: [[-1,-1,2],[-1,0,1]]
Test #2No triplet sums to zero
Input: [[0,1,1]]
Output: []
Test #3Many ways, one triplet
Input: [[0,0,0,0]]
Output: [[0,0,0]]
← All challenges