# LeetCode 611: Valid Triangle Number

## Problem Restatement

We are given an integer array `nums`.

Each value can be treated as a side length.

We need to count how many triplets can form a valid triangle. A triplet means choosing three different indices from the array.

The official problem asks us to return the number of triplets chosen from `nums` that can make triangles if we take them as side lengths. The constraints are `1 <= nums.length <= 1000` and `0 <= nums[i] <= 1000`.

## Input and Output

Function signature:

```python
def triangleNumber(nums: list[int]) -> int:
    ...
```

Input:

| Parameter | Meaning |
|---|---|
| `nums` | Array of side lengths |

Output:

| Type | Meaning |
|---|---|
| `int` | Number of valid triangle triplets |

## Examples

Example 1:

```python
nums = [2, 2, 3, 4]
```

Valid triplets are:

| Triplet | Reason |
|---|---|
| `(2, 2, 3)` | `2 + 2 > 3` |
| `(2, 3, 4)` using first `2` | `2 + 3 > 4` |
| `(2, 3, 4)` using second `2` | `2 + 3 > 4` |

Output:

```python
3
```

Example 2:

```python
nums = [4, 2, 3, 4]
```

After sorting:

```python
[2, 3, 4, 4]
```

Valid triplets are:

| Triplet | Valid? |
|---|---|
| `(2, 3, 4)` | Yes |
| `(2, 3, 4)` | Yes |
| `(2, 4, 4)` | Yes |
| `(3, 4, 4)` | Yes |

Output:

```python
4
```

## First Thought: Check Every Triplet

The direct solution is to try every possible group of three indices.

For each triplet, check the triangle inequality:

```python
a + b > c
a + c > b
b + c > a
```

This works, but it uses three nested loops.

For an array of length `n`, the time complexity is:

```text
O(n^3)
```

Since `n` can be up to `1000`, this is too slow.

## Key Insight

Sort the array first.

After sorting, suppose we choose three sides:

```text
a <= b <= c
```

Then we only need to check one condition:

```text
a + b > c
```

The other two are automatically true because `c` is the largest side.

So the problem becomes:

For each largest side `c`, count how many pairs `(a, b)` before it satisfy:

```text
a + b > c
```

This is a two-pointer problem.

## Algorithm

Sort `nums`.

Then fix the largest side by index `k`, moving from right to left.

For each `k`:

1. Set `left = 0`.
2. Set `right = k - 1`.
3. While `left < right`:
   - If `nums[left] + nums[right] > nums[k]`, then every value from `left` through `right - 1` can pair with `nums[right]`.
   - Add `right - left` to the answer.
   - Move `right` leftward.
   - Otherwise, the sum is too small, so move `left` rightward.

Why can we add `right - left`?

Because the array is sorted.

If:

```python
nums[left] + nums[right] > nums[k]
```

then for every index `i` where:

```text
left <= i < right
```

we also have:

```python
nums[i] + nums[right] >= nums[left] + nums[right] > nums[k]
```

So all those pairs are valid.

## Implementation

```python
class Solution:
    def triangleNumber(self, nums: list[int]) -> int:
        nums.sort()

        count = 0
        n = len(nums)

        for k in range(n - 1, 1, -1):
            left = 0
            right = k - 1

            while left < right:
                if nums[left] + nums[right] > nums[k]:
                    count += right - left
                    right -= 1
                else:
                    left += 1

        return count
```

## Code Explanation

First, sort the array:

```python
nums.sort()
```

Sorting lets us treat `nums[k]` as the largest side when `k` is fixed.

The outer loop chooses the largest side:

```python
for k in range(n - 1, 1, -1):
```

For each largest side, we search for valid pairs in the prefix:

```python
left = 0
right = k - 1
```

Now compare the smallest available side with the current `right` side:

```python
if nums[left] + nums[right] > nums[k]:
```

If this is true, then all pairs:

```text
(left, right), (left + 1, right), ..., (right - 1, right)
```

are valid.

So we add:

```python
count += right - left
```

Then we move `right` leftward:

```python
right -= 1
```

If the sum is too small, we need a larger left side:

```python
else:
    left += 1
```

At the end, `count` contains the number of valid triplets.

## Correctness

After sorting, every triplet chosen with indices `i < j < k` has side lengths:

```text
nums[i] <= nums[j] <= nums[k]
```

So the triplet forms a valid triangle exactly when:

```text
nums[i] + nums[j] > nums[k]
```

The algorithm fixes `k` as the largest side and uses two pointers to count all pairs `(i, j)` with `i < j < k` satisfying that condition.

When `nums[left] + nums[right] > nums[k]`, every index from `left` to `right - 1` also forms a valid pair with `right`, because those values are at least `nums[left]`. The algorithm counts exactly those `right - left` pairs.

When `nums[left] + nums[right] <= nums[k]`, the current `left` value is too small to pair with `right`. Since any smaller or equal left-side candidate would also fail, the algorithm safely moves `left` rightward.

Thus, for each fixed `k`, all valid pairs are counted exactly once. Since every valid triplet has exactly one largest index `k`, the final answer is exactly the number of valid triangle triplets.

## Complexity

Let `n` be the length of `nums`.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2)` | Sorting costs `O(n log n)`, then the two-pointer loops cost `O(n^2)` |
| Space | `O(1)` | Apart from sorting, only counters and pointers are used |

In Python, `sort()` may use additional internal memory, but the algorithm itself uses constant extra space.

## Alternative: Sorting and Binary Search

For each pair `(i, j)`, we can binary search for the largest `k` such that:

```python
nums[i] + nums[j] > nums[k]
```

```python
from bisect import bisect_left

class Solution:
    def triangleNumber(self, nums: list[int]) -> int:
        nums.sort()

        count = 0
        n = len(nums)

        for i in range(n - 2):
            if nums[i] == 0:
                continue

            for j in range(i + 1, n - 1):
                limit = nums[i] + nums[j]
                k = bisect_left(nums, limit, j + 1, n)
                count += k - j - 1

        return count
```

This version is also correct, but it runs in:

```text
O(n^2 log n)
```

The two-pointer solution is faster.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.triangleNumber([2, 2, 3, 4]) == 3
    assert s.triangleNumber([4, 2, 3, 4]) == 4
    assert s.triangleNumber([1, 1, 1, 1]) == 4
    assert s.triangleNumber([0, 0, 0]) == 0
    assert s.triangleNumber([1, 2, 3]) == 0
    assert s.triangleNumber([2, 3, 4, 5, 6]) == 7

    print("all tests passed")

run_tests()
```

Test coverage:

| Case | Why |
|---|---|
| `[2, 2, 3, 4]` | Official-style duplicate-side case |
| `[4, 2, 3, 4]` | Unsorted input |
| All equal sides | Every triplet is valid |
| Zeros only | Degenerate sides cannot form triangles |
| Exact equality `1 + 2 = 3` | Confirms strict inequality |
| Larger mixed case | Checks counting across several largest sides |