Fix one, scan the rest

Turning a three-element search into a two-element one, and handling duplicates without a set.

Key idea

The reduction

Searching for three elements that satisfy a condition looks like a different problem from searching for two. It is not. Fix the first element, and what remains is a two-element search with an adjusted target, which you can already do in O(n).

Doing that for every possible first element gives O(n) choices times O(n) inner scan, so O(n squared) overall. That is the expected complexity for this family, and it beats the O(n cubed) triple loop by exactly the amount the inner two-pointer scan saves.

1def count_triples_summing_to(sorted_values, target):2    """Count index triples i < j < k whose values sum to target."""3    total = 04    for i in range(len(sorted_values) - 2):5        left, right = i + 1, len(sorted_values) - 16        need = target - sorted_values[i]7        while left < right:8            pair = sorted_values[left] + sorted_values[right]9            if pair == need:10                total += 111                left += 112                right -= 113            elif pair < need:14                left += 115            else:16                right -= 117    return total18 19print(count_triples_summing_to([1, 2, 3, 4, 5], 9))

Why it works

Skipping duplicate values

Counting index triples and listing distinct value triples are different questions, and the second one is where duplicates bite. If the input holds two 2s, the same set of values can be reached through different indexes, and a problem asking for distinct results wants it reported once.

The fix is to skip repeated values at each level rather than to deduplicate the results afterward. Sort first so equal values sit together, then at each level, if this value equals the previous one at the same level, move on.

1def distinct_pairs_summing_to(sorted_values, target):2    """Each distinct value pair once, even when values repeat."""3    result = []4    left, right = 0, len(sorted_values) - 15    while left < right:6        total = sorted_values[left] + sorted_values[right]7        if total < target:8            left += 19        elif total > target:10            right -= 111        else:12            result.append([sorted_values[left], sorted_values[right]])13            left += 114            while left < right and sorted_values[left] == sorted_values[left - 1]:15                left += 1          # skip the rest of this run of equal values16            right -= 117    return result18 19print(distinct_pairs_summing_to([1, 1, 2, 2, 3, 3], 4))

Find the bug· 5 min

Find the duplicate-handling bug

This is meant to return each distinct pair once. On the input [1, 1, 2, 2, 3, 3] with target 4 it returns [[1, 3], [1, 3], [2, 2]]. Click the line that causes the repeat.

Click the line you think is wrong

Complexity· 5 min

Cost of fix-one-then-scan

Give the time and space complexity of count_triples_summing_to on an already sorted list of length n, not counting the output.

Problem· 30 min

3sum

Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.

CodeGround