# 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

## Problem

Given a list of integers and target k, return all unique triplets (a, b, c) with a <= b <= c whose sum equals k. Each triplet is a 3-element list. Return the list of triplets sorted lexicographically, with no duplicate triplets.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests the **three-sum** pattern with **sorting and two pointers**. It is identical in structure to the classic 3-sum problem and probes the candidate's ability to handle duplicate elimination and pointer mechanics.

> **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 three_sum(nums: list, k: int) -> list:
    nums.sort()
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        left = i + 1
        right = 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). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.