two-pointers · Problem 2 of 4

Three Sum

medium
Meta logoMeta
Amazon logoAmazon
Apple logoApple
Google logoGoogle

Given an array of integers nums, return all unique triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

The solution set must not contain duplicate triplets.

threeSum([-1, 0, 1, 2, -1, -4])  ->  [[-1, -1, 2], [-1, 0, 1]]
threeSum([0, 1, 1])               ->  []
threeSum([0, 0, 0])               ->  [[0, 0, 0]]

Your solution

Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.

Running is free — Submit is what records it. Or press ⌘↩

Tests

5 cases, 2 hidden
calltypeexpectedresult
threeSum([-1,0,1,2,-1,-4])standard mixed[[-1,-1,2],[-1,0,1]]—
threeSum([0,1,1])no solution[]—
threeSum([0,0,0])all zeros[[0,0,0]]—
withheldhiddenwithheld—
withheldhiddenwithheld—

Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.

Complexity

target time
O(n^2)
target space
O(1) extra space (or O(n) depending on sort implementation)

Sorting takes O(n log n), and the outer loop with two-pointer inner scan takes O(n^2), dominating the time.

Hints

Stuck? Hints open one at a time, each giving a little more away.

3 hints left