# Valid Triangle Number
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/valid-triangle-number)
Canonical: https://scaleengineer.com/dsa/problems/valid-triangle-number
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Expedia](https://scaleengineer.com/companies/expedia), [LinkedIn](https://scaleengineer.com/companies/linkedin)
---
## Problem
Given an integer array `nums`, return _the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle_.

**Example 1:**

**Input:** nums = [2,2,3,4]
**Output:** 3
**Explanation:** Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

**Example 2:**

**Input:** nums = [4,2,3,4]
**Output:** 4

**Constraints:**

* `1 <= nums.length <= 1000`
* `0 <= nums[i] <= 1000`

# Approaches
## Brute Force
The most straightforward approach is to check every possible triplet of numbers from the array and verify if they can form a valid triangle. This involves iterating through all combinations of three elements and applying the triangle inequality theorem.
**Time:** O(N^3), where N is the number of elements in `nums`. The three nested loops result in a cubic number of checks. · **Space:** O(1) extra space, as we only use a few variables to store indices and the count.
**Pros:** Simple to understand and implement.; Does not require any modification to the input array.
**Cons:** Extremely inefficient due to its cubic time complexity.; Likely to cause a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints (N up to 1000).
### Explanation
This method uses three nested loops to generate all unique triplets `(nums[i], nums[j], nums[k])` from the input array. For each triplet, we must verify that it can form a triangle. According to the triangle inequality theorem, the sum of the lengths of any two sides of a triangle must be greater than the length of the third side. Therefore, for a triplet `(a, b, c)` to be valid, it must satisfy `a + b > c`, `a + c > b`, and `b + c > a`. We maintain a counter, which is incremented for every triplet that satisfies these three conditions. While simple, this approach is very slow because it checks a number of triplets proportional to N cubed.

```java
class Solution {
    public int triangleNumber(int[] nums) {
        int count = 0;
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] + nums[j] > nums[k] && 
                        nums[i] + nums[k] > nums[j] && 
                        nums[j] + nums[k] > nums[i]) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use three nested loops to select three distinct indices `i`, `j`, and `k` from the array, such that `i < j < k`.
- Let the side lengths be `a = nums[i]`, `b = nums[j]`, and `c = nums[k]`.
- For each triplet, check if it satisfies all three conditions of the triangle inequality theorem: `a + b > c`, `a + c > b`, and `b + c > a`.
- If all conditions are met, increment the `count`.
- After checking all possible triplets, return `count`.

## Brute Force with Sorting
This approach is a refinement of the brute-force method. By first sorting the array, we can simplify the triangle inequality check. If the side lengths `a, b, c` are sorted such that `a <= b <= c`, we only need to check if `a + b > c`.
**Time:** O(N^3). Sorting takes O(N log N), but it is dominated by the three nested loops, which run in O(N^3) time. · **Space:** O(log N) or O(N), depending on the space complexity of the sorting algorithm used. For instance, Java's `Arrays.sort` for primitives uses a Dual-Pivot Quicksort which takes O(log N) space on average.
**Pros:** Slightly more optimized than the naive brute-force due to a simpler check.; The logic inside the loops is cleaner.
**Cons:** The time complexity is still O(N^3) in the worst case, which is too slow for large inputs.; Requires modifying the input array by sorting it, or using extra space for a sorted copy.
### Explanation
The key insight here is that for three sorted side lengths `a <= b <= c`, the conditions `a + c > b` and `b + c > a` are always true (assuming positive lengths). Thus, the triangle inequality check reduces to a single condition: `a + b > c`.

The algorithm starts by sorting the `nums` array. Then, it proceeds with three nested loops to pick triplets `(nums[i], nums[j], nums[k])` with `i < j < k`. Because the array is sorted, we are guaranteed that `nums[i] <= nums[j] <= nums[k]`. Inside the innermost loop, we just check if `nums[i] + nums[j] > nums[k]`. If it is, we increment our count. This reduces the number of comparisons inside the loop, but the overall number of triplets to check remains the same, leading to a cubic time complexity.

```java
import java.util.Arrays;

class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            if (nums[i] == 0) continue; // Optimization for zero-length sides
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] + nums[j] > nums[k]) {
                        count++;
                    } else {
                        // If it fails for this k, it will fail for all subsequent k's
                        break;
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- First, sort the input array `nums` in non-decreasing order.
- Initialize a counter `count` to 0.
- Use three nested loops to iterate through triplets `(i, j, k)` with `i < j < k`.
- Since the array is sorted, `nums[i] <= nums[j] <= nums[k]`. We only need to check the condition `nums[i] + nums[j] > nums[k]`.
- If the condition is met, we have found a valid triangle, so we increment `count`.
- An optional optimization: if `nums[i] + nums[j] <= nums[k]`, we can break the innermost loop (over `k`) because any subsequent element `nums[k']` (where `k' > k`) will also not satisfy the condition.
- Return `count` after all loops complete.

## Two Pointers with Sorting
The most efficient solution involves sorting the array and then using a two-pointer technique. By fixing the largest side of the potential triangle, we can efficiently find the number of valid pairs for the other two sides in linear time, leading to an overall quadratic time complexity.
**Time:** O(N^2). Sorting takes O(N log N). The nested loop structure with the two-pointer scan takes O(N^2), which dominates the overall complexity. · **Space:** O(log N) or O(N), for the space used by the sorting algorithm.
**Pros:** Highly efficient with a quadratic time complexity.; This is the optimal approach for the given constraints.
**Cons:** The logic is more complex than the brute-force approaches.; Requires sorting, which alters the original array or needs extra space.
### Explanation
This approach significantly improves performance by reducing the search space. After sorting the array `nums`, we iterate from the end of the array to fix the largest side of the triangle, `c = nums[k]`. For each `c`, we need to find the number of pairs `(a, b)` from the subarray `nums[0...k-1]` such that `a + b > c`.

This subproblem is solved efficiently using two pointers, `left` starting at `0` and `right` at `k-1`. 
- If `nums[left] + nums[right] > nums[k]`, we have found a valid pair. Crucially, any element `nums[i]` where `left <= i < right` will also satisfy `nums[i] + nums[right] > nums[k]` because `nums[i] >= nums[left]`. This means we have found `right - left` valid triangles. We add this to our count and decrement `right` to see if a smaller `b` can also form a triangle.
- If `nums[left] + nums[right] <= nums[k]`, the sum is too small. To increase the sum, we must use a larger `a`, so we increment `left`.
This process continues until `left` and `right` cross. Since the two-pointer scan takes O(k) time for each `k`, the total time complexity is O(N^2).

```java
import java.util.Arrays;

class Solution {
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return 0;
        }
        Arrays.sort(nums);
        int count = 0;
        for (int k = n - 1; k >= 2; k--) {
            int left = 0;
            int right = k - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[k]) {
                    count += (right - left);
                    right--;
                } else {
                    left++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Sort the input array `nums`.
- Initialize a counter `count` to 0.
- Iterate backwards through the array with an index `k` from `n-1` down to `2`. `nums[k]` will be considered as the largest side `c` of a potential triangle.
- For each `k`, use two pointers, `left = 0` and `right = k - 1`, to find pairs `(a, b)` in the subarray `nums[0...k-1]`.
- While `left < right`:
  - If `nums[left] + nums[right] > nums[k]`, a valid triangle is formed. Since the array is sorted, `nums[right]` paired with any element from `nums[left]` to `nums[right-1]` will also form a valid triangle with `nums[k]`. There are `right - left` such pairs. Add this number to `count` and decrement `right` to check for pairs with a smaller second side.
  - If `nums[left] + nums[right] <= nums[k]`, the sum is too small. Increment `left` to try and find a larger sum.
- Return the total `count`.

# Solutions
### Java

```java
class Solution {
public
  int triangleNumber(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    int res = 0;
    for (int i = n - 1; i >= 2; --i) {
      int l = 0, r = i - 1;
      while (l < r) {
        if (nums[l] + nums[r] > nums[i]) {
          res += r - l;
          --r;
        } else {
          ++l;
        }
      }
    }
    return res;
  }
}

```

### Python

```python
class Solution:
    def triangleNumber(self, nums: List[int]) -> int: nums . sort() ans, n = 0, len(nums) for i in range(n - 2): for j in range(i + 1, n - 1): k = bisect_left(nums, nums[i] + nums[j], lo=j + 1) - 1 ans += k - j return ans

```

### CPP

```cpp
class Solution { public: int triangleNumber ( vector < int >& nums ) { sort ( nums . begin (), nums . end ()); int ans = 0 , n = nums . size (); for ( int i = 0 ; i < n - 2 ; ++ i ) { for ( int j = i + 1 ; j < n - 1 ; ++ j ) { int k = lower_bound ( nums . begin () + j + 1 , nums . end (), nums [ i ] + nums [ j ]) - nums . begin () - 1 ; ans += k - j ; } } return ans ; } };
```