The Triple Alliance

A hard Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
hard
Seniority
L4
Asked in
Junglee Games

Problem

In ledger reconciliation the same amount can land on many lines and some entries are credits, so the input list nums may hold duplicate and negative values. Given nums and a target k, return each trio of values taken from three distinct positions that sums to k, every trio ordered smallest value first and trios sharing the same three values collapsed to one. Return the trios ordered from the smallest value-list to the largest.

Three numbers, one target.

Example 1

Input:

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

Output:

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

Example 2

Input:

nums = [2,2,2,3,4], k = 8

Output:

[[2,2,4]]

Worked solution and explanation

What this really is

Strip the ledger framing and this is the classic three-sum: find every unique value triplet that adds up to k. Anyone can write the O(n^3) brute force with three nested loops, and most candidates do in the first thirty seconds. What actually separates people is two moves: collapsing it to O(n^2) by sorting and walking a pair of pointers inward, and getting the duplicate-skipping exactly right. Botch the dedup and you either emit the same triplet twice or step over a valid one, and the interviewer spots it the moment they read your output.

How to get there

Step 1: Sort the values

A sorted copy turns 'find a pair that sums to k minus nums[i]' into a convergence problem and parks every duplicate right next to its twin. Sort a copy rather than mutating the caller's list.

Step 2: Fix the first value, converge the other two

For each index i, point left just past i and right at the end. If the three values overshoot k, pull right in; if they fall short, push left out; if they hit it, record the triplet. Each i costs one linear sweep, so the whole scan is O(n^2).

Step 3: Skip duplicates at all three positions

This is where it bites. After recording a hit, walk left and right past any equal neighbors, and skip an i that equals the previous i. Miss any one of the three skips and duplicate value-lists leak into the result.

The solution

Sort, then fix-one with a two-pointer sweep
def triplets_sum_to_k(nums: list[int], k: int) -> list[list[int]]:
    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, right = i + 1, 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

Outer loop fixes the smallest value; the inner pointers converge. The three skip blocks keep value-lists unique.

Common follow-up questions