# Triangle Validator

> Not every triangle is a triangle.

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

Domain: Python · Difficulty: medium · Seniority: L5

## Problem

Given a list of positive lengths, return the count of unique triplets (i<j<k) where lengths[i]+lengths[j]>lengths[k] AND the two similar triangle inequalities hold.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests the **triangle inequality** combined with **sorting and two-pointer counting**. The brute-force O(n^3) approach is straightforward, but the O(n^2) optimized version probes whether a candidate can use sorted order to count valid triplets efficiently.

> **Trick to Solving**
>
> Sort the array. For each pair (i, j), binary search or two-pointer scan for the largest k where `lengths[i] + lengths[j] > lengths[k]`. All elements between j+1 and k form valid triplets with (i, j).

---

### Break down the requirements

#### Step 1: Sort the rod lengths

Sorting lets you fix the two smaller sides and binary search for the maximum valid third side.

#### Step 2: For each pair, count valid third sides

If `a + b > c` (where c is the largest), the triangle inequality holds. With sorted data, all values between j+1 and the found boundary are valid.

---

### The solution

**Sort with two-pointer triangle counting**

```python
def count_triangles(lengths: list) -> int:
    lengths.sort()
    n = len(lengths)
    count = 0
    for i in range(n - 2):
        k = i + 2
        for j in range(i + 1, n - 1):
            while k < n and lengths[i] + lengths[j] > lengths[k]:
                k += 1
            count += k - j - 1
    return count
```

> **Time and Space Complexity**
>
> **Time:** O(n^2). The outer loop is O(n), the inner loop with advancing k pointer is amortized O(n).
> 
> **Space:** O(1) auxiliary (in-place sort).

> **Interviewers Watch For**
>
> The key insight is that k only advances forward for a fixed i. When j increments, k does not reset, because increasing j (the second side) can only increase the valid range.

> **Common Pitfall**
>
> Checking all three triangle inequality conditions. With sorted data, if `a + b > c` where `a <= b <= c`, the other two conditions are automatically satisfied.

---

## Common follow-up questions

- Why is checking only `a + b > c` sufficient when sorted? _(Tests that `a + c > b` and `b + c > a` are guaranteed when `c >= b >= a`.)_
- What if you needed to return the actual triplets? _(Tests collecting indices or values instead of just counting.)_
- What if lengths could be zero? _(Tests that zero-length sides never form valid triangles.)_
- How would you handle very large inputs (millions of rods)? _(Tests that O(n^2) is likely acceptable for n up to ~10^4 but may need optimization for larger inputs.)_

## Related

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