# The Triplet Hunt

> Every path that works gets a seat at the table.

Canonical URL: <https://datadriven.io/problems/the_triplet_hunt>

Domain: Python · Difficulty: medium · Seniority: L5 · Asked in: Ripple

## Problem

You are reconciling a ledger: `nums` is a list of integer adjustments and `k` is a target balance. Return every unique trio of values that together sum to `k`, each trio listed from its smallest value to its largest. The same three values never appear twice, and the trios come back in ascending order.

## Example 1

Input:

```
nums = [-4,-1,-1,0,1,2], k = 0
```

Output:

```
[[-1,-1,2],[-1,0,1]]
```

## Example 2

Input:

```
nums = [1,2,3,4,5], k = 9
```

Output:

```
[[1,3,5],[2,3,4]]
```

## Worked solution and explanation

### What this really is

Strip the ledger framing and this is 3-sum: find every unique value-trio that hits a target. Everyone reaches for the triple loop; what separates candidates is killing duplicate trios without leaning on a set of tuples. Sort first, fix the smallest element, then sweep the rest from both ends. The trap is the dedup: skip equal values at the fixed index AND after each hit, or you emit [-1, 0, 1] twice and fail on any input with repeats.

> **Trick to Solving**
>
> Sort, fix one index, then two-pointer scan the remaining range. Skip duplicate values at every level to guarantee unique sorted triplets without extra data structures.

---

### Break down the requirements

#### Step 1: Sort the input

Sorting enables two-pointer search and makes duplicate detection trivial.

#### Step 2: Outer loop fixes one element; inner loop uses two pointers

For each i, search `[i+1, n-1]` for pairs summing to `k - nums[i]`.

#### Step 3: Skip duplicates at all levels

Advance past repeated values after recording each triplet.

---

### The solution

**Sorted array with fix-one two-pointer search**

```python
def the_triplet_hunt(nums: list[int], k: int) -> list[list[int]]:
    nums.sort()
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == k:
                triplets.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left + 1]:
                    left += 1
                while left < right and nums[right] == nums[right - 1]:
                    right -= 1
                left += 1
                right -= 1
            elif total < k:
                left += 1
            else:
                right -= 1
    return triplets
```

> **Time and Space Complexity**
>
> **Time:** O(n^2). Sorting is O(n log n), the nested scan is O(n^2) which dominates.
> 
> Space: O(1) auxiliary beyond the result list, since sorting is in-place.

> **Interviewers Watch For**
>
> In-place sort mutates the input. Candidates should mention this tradeoff and offer to sort a copy if input preservation matters.

> **Common Pitfall**
>
> Off-by-one in the duplicate skip. Using `nums[left] == nums[left + 1]` requires `left < right` as a guard to prevent index-out-of-bounds.

---

## Common follow-up questions

- How would you find quadruplets instead? _(Tests nesting one more loop for O(n^3) or using a pair-sum hashmap.)_
- What if the input could contain up to 10^5 elements? _(Tests that O(n^2) is 10^10 operations, which is too slow, requiring problem-specific optimizations.)_
- What if k is always 0? _(Tests that the algorithm handles negative numbers symmetrically and zero targets naturally.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_triplet_hunt)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.