Return Unique Three-Sum Value Triples
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Return Unique Three-Sum Value Triples
### Problem
Implement `threeSumTarget(nums, target) -> triples`.
Return every distinct value triple `[a, b, c]` for which three distinct input indices exist, `a <= b <= c`, and `a + b + c == target`.
Each value triple must appear exactly once even when the input contains duplicates. Sort the returned triples lexicographically. Return `[]` when no triple exists, and do not mutate `nums`.
### Constraints
- `0 <= nums.length <= 2,000`.
- `-1,000,000,000 <= nums[i], target <= 1,000,000,000`.
- Use signed 64-bit arithmetic for sums.
- Target `O(n^2 + P)` time after sorting, where `P` is the number of returned triples, and `O(n + P)` space including the result.
```hint Separate index use from output identity
Trace an input containing four copies of one value and decide which repeated index choices collapse to the same canonical value triple.
```
### Examples
```text
nums = [-1, 0, 1, 2, -1, -4]
target = 0
triples = [[-1, -1, 2], [-1, 0, 1]]
```
```text
nums = [2, 2, 2, 2]
target = 6
triples = [[2, 2, 2]]
```
```text
nums = [1, 2]
target = 3
triples = []
```
### Discussion Requirements
- Explain how duplicate values are skipped without losing a valid repeated-value triple.
- Compare the quadratic approach with extending the hash-based two-sum strategy for each fixed first element.
Quick Answer: Return all unique value triples that reach a target using three distinct input positions, with canonical ordering despite duplicate values. Candidates are evaluated on duplicate control, overflow-safe sums, nonmutation, output-sensitive complexity, and careful boundary cases.
Given an integer array `nums` and an integer `target`, return every distinct **value triple** `[a, b, c]` for which all three of the following hold:
- three **distinct indices** `i`, `j`, `k` of `nums` exist whose values are `a`, `b`, and `c` (counted with multiplicity);
- `a <= b <= c`;
- `a + b + c == target`.
Identity is by value, not by index. Two triples are the same triple when they hold the same three values with the same multiplicities, so each value triple appears **exactly once** in the result no matter how many index choices produce it. A value may be repeated inside one triple only as often as it occurs in `nums`: `[2, 2, 2]` is reportable only when `nums` contains at least three copies of `2`.
Return the triples sorted **lexicographically**: compare first elements, then second elements, then third elements. Every triple is internally sorted (`a <= b <= c`) before this comparison. Return the empty list `[]` when no triple exists. `nums` must not be mutated; the returned list is the only graded artifact.
### Examples
**Example 1**
```
Input: nums = [-1, 0, 1, 2, -1, -4], target = 0
Output: [[-1, -1, 2], [-1, 0, 1]]
```
The two copies of `-1` sit at different indices, so `[-1, -1, 2]` is legal. `[-1, 0, 1]` can be formed with either copy of `-1`, yet it is reported once. Lexicographically `[-1, -1, 2]` precedes `[-1, 0, 1]` because the first elements tie and `-1 < 0`.
**Example 2**
```
Input: nums = [2, 2, 2, 2], target = 6
Output: [[2, 2, 2]]
```
Four different index choices `{0,1,2}`, `{0,1,3}`, `{0,2,3}`, `{1,2,3}` all describe the same value triple, which is therefore emitted a single time.
**Example 3**
```
Input: nums = [1, 2], target = 3
Output: []
```
Fewer than three indices exist, so no triple can be formed.
### Constraints
- `0 <= nums.length <= 2000`
- `-10^9 <= nums[i] <= 10^9`
- `-10^9 <= target <= 10^9`
- Every value crossing the function boundary (each input element and each returned triple element) fits a signed 32-bit integer, but a three-term sum reaches `3 * 10^9` and does **not**. Accumulate sums in signed 64-bit arithmetic (`long` in Java, `long long` in C++); `3 * 10^9` is far below `2^53`, so JavaScript numbers stay exact.
- Target `O(n^2 + P)` time after sorting and `O(n + P)` space, where `n = nums.length` and `P` is the number of returned triples.
Constraints
- 0 <= nums.length <= 2000
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- Each input element and each returned triple element fits a signed 32-bit integer, but a three-term sum reaches 3 * 10^9 and must be accumulated in signed 64-bit arithmetic (long in Java, long long in C++); 3 * 10^9 is far below 2^53 so JavaScript numbers remain exact
- Each triple is internally non-decreasing (a <= b <= c) and the outer list is sorted lexicographically
- Each distinct value triple appears exactly once; return [] when no triple exists
- nums must not be mutated
- Target O(n^2 + P) time after sorting and O(n + P) space, where n = nums.length and P is the number of returned triples
Examples
Input: ([], 0)
Expected Output: []
Input: ([5], 5)
Expected Output: []
Hints
- Sorting a copy of the array first makes the inner search monotone: with the smallest element of the triple fixed, the remaining two can be found by walking one pointer up from the left and one down from the right of the suffix.
- Deduplication happens in two places -- the fixed first element, and the two elements the inward scan lands on after a hit. Only skip a repeated value once that value has already been used in the position you are advancing past, or you will delete legitimate triples such as [x, x, y].
- Trace [2, 2, 2, 2] with target 6 and then [2, 2] with target 6: the first must report one triple and the second none, which is what pins 'three distinct indices' as separate from 'three distinct values'.