The Question

3Sum

Given an integer array, return all unique triplets that sum to zero, ensuring no duplicate triplets appear in the result.

Java

Two Pointers

Sorting

Implementation Breakdown

Problem Set

Goal: Find all unique triplets

[nums[i], nums[j], nums[k]]

such that their sum is zero.

Constraints:

Indices

i, j, k

must be distinct.

The output must not contain duplicate triplets (e.g., if [-1, 0, 1] is found, [0, -1, 1] should not be added).

Array size

n

can be up to

3000

Element values range from

-10^5

to .

Approach

To efficiently find triplets and avoid duplicates, we sort the array first.

We iterate through the array, fixing one element i. For the remaining part of the array to the right of i, we use a Two Pointers approach to find two numbers that sum to -nums[i].

To prevent duplicates:

Skip the same value for the fixed element i.

After finding a valid triplet, skip the same values for both left and right pointers.

Algorithm: Sorting + Two Pointers.

Data Structure: ArrayList (for result), int[] (input).

Complexity:

Time:

O(N^2)

where

N

is the number of elements (Sorting is

O(N \log N)

, nested loops are

O(N^2)

Space:

O(\log N)

O(N)

depending on the sorting implementation's auxiliary space.