Find all unique triplets summing to zero
Company: NVIDIA
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Problem
Given an integer array `nums`, return **all unique triplets** `[nums[i], nums[j], nums[k]]` such that:
- `i`, `j`, and `k` are **distinct indices** (`i != j != k`), and
- `nums[i] + nums[j] + nums[k] == 0`.
The returned triplets must be **unique** (i.e., no duplicate triplets in the output). Triplets can be returned in any order.
## Input
- `nums`: an array of integers
## Output
- A list/array of unique triplets, each triplet containing three integers whose sum is zero
## Constraints (typical interview bounds)
- `0 <= nums.length <= 3000`
- `-10^5 <= nums[i] <= 10^5`
## Example
- Input: `nums = [-1, 0, 1, 2, -1, -4]`
- Output: `[[-1, -1, 2], [-1, 0, 1]]`
Quick Answer: This question evaluates array-based algorithm design, handling of duplicate results, and analysis of time and space complexity when producing unique triplets that sum to zero.
Given an integer array `nums`, return all unique triplets `[nums[i], nums[j], nums[k]]` such that `i`, `j`, and `k` are distinct indices and `nums[i] + nums[j] + nums[k] == 0`.
To make the output deterministic, return each triplet in non-decreasing order, and return the full list of triplets in lexicographic order. Do not include duplicate triplets.
Constraints
- 0 <= len(nums) <= 3000
- -100000 <= nums[i] <= 100000
Examples
Input: ([-1, 0, 1, 2, -1, -4],)
Expected Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation: The only unique triplets that sum to zero are [-1, -1, 2] and [-1, 0, 1].
Input: ([0, 0, 0, 0],)
Expected Output: [[0, 0, 0]]
Explanation: Even though there are multiple ways to choose three zeros, they all form the same triplet, so it appears once.
Hints
- Sorting the array helps you avoid duplicates and makes it possible to use a two-pointer scan.
- Fix one number, then look for two remaining numbers whose sum equals its negation.