# Three That Hold

> Not every triangle is a triangle.

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

Domain: Python · Difficulty: medium · Seniority: L5

## 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.

## 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.

> **Trick to solving**
>
> Sort first. Once the rods are ordered, fix the longest side of the candidate triangle and ask which pairs of shorter rods sum past it. Sorting turns 'check three inequalities' into 'check one'.

### 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**

```python
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
```

> **Time and space**
>
> Time: O(n^2). The outer loop fixes each largest side in O(n); for each one the two pointers traverse the prefix once, O(n). Space: O(1) auxiliary on top of the in-place sort. For n up to 1,000 that is about a million comparisons, instant.

> **Interviewers watch for**
>
> The `count += hi - lo` jump. A candidate who increments by one per valid pair is really running the O(n^3) loop in disguise. Adding the whole run at once is the move that proves you understood why sorted order lets you count instead of enumerate.

> **Common pitfall**
>
> Two classic slips. First, checking all three inequalities anyway, which is harmless but signals you missed why sorting helps. Second, counting ordered permutations: each unordered triplet of positions is one triangle, so (0,1,2) and (2,1,0) must not both count. The two-pointer structure gives unordered combinations for free.

**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

- Why is checking only the two smaller sides against the largest enough once sorted? _(Tests that a+c>b and b+c>a are guaranteed when c is the largest.)_
- What if you had to return the actual triplets, not just how many? _(Tests returning the index triplets instead of a bare count, which forces enumeration and changes the complexity story.)_
- How does the answer change if a side length could be zero? _(Tests handling of degenerate sides and the strict-versus-non-strict boundary.)_
- How would you scale this to millions of rods? _(Tests awareness that O(n^2) is fine here but would not survive millions of rods, prompting bucketing or approximate approaches.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/three_that_hold)
- [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). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.