Three That Hold

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

Domain
Python
Difficulty
medium
Seniority
L5
Asked in
Airbnb

Problem

You're auditing a batch of rod lengths pulled from a parts inventory to see how many real triangles could be built from them. Count the groups of three rods that can form a valid triangle, where each side must be shorter than the sum of the other two. Rods sitting at different positions count as separate groups even when their lengths match, and the order of sides within a group does not matter.

Not every triangle is a triangle.

Example 1

Input:

lengths = [3,4,5,6]

Output:

4

Example 2

Input:

lengths = [1,2,3]

Output:

0

Worked solution and explanation

What this really is

Strip the inventory costume off and this is 'count the triplets whose two smaller values sum past the largest one.' The thing being probed is whether you see that the three triangle-inequality checks collapse into one once the sides are in order. Almost everyone writes the triple loop that tests all three inequalities; the candidates who stand out realize that after sorting, a <= b <= c, so a + c > b and b + c > a are free, and only a + b > c can ever fail. Miss that and you do three times the comparisons and still reach for an O(n^3) loop when an O(n^2) sweep was sitting right there.

Building the fast version

Step 1: Sort the rod lengths

With lengths ascending, every triplet you pick has a well-defined largest side, and you only ever have to test the sum of the two smaller ones against it.

Step 2: Fix the longest side, then squeeze from both ends

Walk the largest side from the end of the array inward. For that fixed largest, put one pointer at the smallest rod and one just below the largest, then close them in. This is the classic two-pointer sweep.

Step 3: Count a whole run at once

When the two pointers satisfy lengths[lo] + lengths[hi] > lengths[largest], then every rod between lo and hi also works with hi, because they are all at least as large as the one at lo. So add hi - lo in one shot and step hi down. If the sum is too small, the only fix is a bigger small side, so advance lo.

Sorted two-pointer triangle count
def triangle_validator(lengths: list[int]) -> int:
    lengths.sort()
    n = len(lengths)
    count = 0
    for largest in range(n - 1, 1, -1):
        lo, hi = 0, largest - 1
        while lo < hi:
            if lengths[lo] + lengths[hi] > lengths[largest]:
                count += hi - lo
                hi -= 1
            else:
                lo += 1
    return count
Brute force
Three nested loops over i<j<k, testing the inequality on every triplet. O(n^3). At n=1000 that is ~10^8 triplets and starts to drag.
Sorted two-pointer
Sort, then for each largest side close two pointers inward, counting runs in bulk. O(n^2), ~10^6 steps at n=1000, and no triplet is ever materialized.

Common follow-up questions