# The Triple Alliance

> Three numbers, one target.

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

Domain: Python · Difficulty: hard · Seniority: L4

## Problem

Given a list of integers and integer k, find all unique triplets of distinct indices whose values sum to k. Each triplet value list is sorted ascending. Return the list of triplets sorted lexicographically. Do not return duplicate value triplets.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests the **three-sum** algorithm, combining **sorting** with the **two-pointer technique**. It is a canonical interview problem that probes duplicate handling, pointer manipulation, and reducing O(n^3) brute force to O(n^2).

> **Trick to Solving**
>
> Sort the array first. Fix one element, then use two pointers on the remaining subarray to find pairs that complete the target sum. Skip duplicate values at each level to avoid duplicate triplets.

---

### Break down the requirements

#### Step 1: Sort the input array

Sorting enables the two-pointer approach and simplifies duplicate skipping.

#### Step 2: Fix one element and two-pointer scan the rest

For each index i, set `left = i + 1` and `right = n - 1`. Adjust pointers based on the current sum.

#### Step 3: Skip duplicates at all three positions

After finding a valid triplet, advance all three pointers past duplicate values.

---

### The solution

**Sort then fix-one with two-pointer scan**

```python
def three_sum(nums: list, k: int) -> list:
    nums_sorted = sorted(nums)
    n = len(nums_sorted)
    triplets = []
    for i in range(n - 2):
        if i > 0 and nums_sorted[i] == nums_sorted[i - 1]:
            continue
        left = i + 1
        right = n - 1
        while left < right:
            total = nums_sorted[i] + nums_sorted[left] + nums_sorted[right]
            if total == k:
                triplets.append([nums_sorted[i], nums_sorted[left], nums_sorted[right]])
                while left < right and nums_sorted[left] == nums_sorted[left + 1]:
                    left += 1
                while left < right and nums_sorted[right] == nums_sorted[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) where n is the array length. The outer loop is O(n) and the inner two-pointer scan is O(n).
> 
> **Space:** O(n) for the sorted copy and result list.

> **Interviewers Watch For**
>
> The duplicate skipping logic is the hardest part. Skipping at the outer loop (`if i > 0 and nums_sorted[i] == nums_sorted[i-1]`) and at both inner pointers is required for correctness.

> **Common Pitfall**
>
> Using a set of tuples to deduplicate is correct but slower. The pointer-based skip is O(1) per skip and avoids the overhead of hashing triplets.

---

## Common follow-up questions

- What if you needed four-sums instead of three? _(Tests adding another outer loop, giving O(n^3), or using a hashmap of pair sums for O(n^2).)_
- What if the array is very large (millions of elements)? _(Tests whether the O(n^2) approach is acceptable or if approximation is needed.)_
- Can you prove that O(n^2) is optimal for three-sum? _(Tests theoretical CS knowledge: no sub-quadratic algorithm is known for the general case.)_
- What if you needed the count of triplets, not the triplets themselves? _(Tests that counting can use the same approach but avoids materializing the result list.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_triple_alliance)
- [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.