Problem Statement

Given an integer array nums, return all unique triplets [a, b, c] such that a + b + c == 0.

Each triplet must be in non-decreasing order (i.e., a ≤ b ≤ c), and the answer must not contain duplicate triplets.

Example 1

Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 1], [-1, 0, 1]]

Explanation:

The triplets that sum to 0 and are unique are [-1, -1, 2] (not valid because it sums to 0?—actually it sums to 0? Wait, it sums to 0? -1 + -1 + 2 = 0. Yes valid, but it’s not in the classic result because there’s no 2? In given array there is 2, so correct valid sets are [-1,-1,2] and [-1,0,1]. If you prefer canonical LeetCode example output: [[-1,-1,2], [-1,0,1]].)

Example 2

Input: nums = [0, 1, 1]
Output: []

Explanation:

No triplet sums to 0.

HINT: Use sorting + two pointers to find pairs for each fixed first element:

Sort nums in non-decreasing order.
For each index i in [0 .. n-3]:

If i > 0 and nums[i] == nums[i-1], continue (skip duplicate anchors).
Set l = i + 1, r = n - 1.
While l < r:
Let sum = nums[i] + nums[l] + nums[r].
If sum == 0, push [nums[i], nums[l], nums[r]], then increment l and decrement r, skipping duplicates at both sides.
Else if sum < 0, increment l.
Else decrement r.

Return the collected list of triplets.

Time & Space Complexity

Time Complexity: O(n^2) — sorting is O(n log n), the main loop with two-pointer per i is O(n^2) overall.
Space Complexity: O(1) extra (ignoring output), since we sort in place and use constant auxiliary memory.

Loading...

Top 10 Array Questions with Solutions - Medium Level

Questions & Code Solutions

Table of Contents