<p>Given an integer array <code>nums</code>, return <em>the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,2,3,4]
<strong>Output:</strong> 3
<strong>Explanation:</strong> Valid combinations are: 
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,2,3,4]
<strong>Output:</strong> 4
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 1000</code></li>
</ul>

class Solution:
    def triple_is_valid(self, a, b, c):
        return a + b > c # and a + c > b and b + c > a
        # we just need to satisfy a + b > c

    def triangleNumber(self, nums: List[int]) -> int:
        """ brute force try everything. TLE """
        ways = 0
        nums.sort() # 2,3,4,4
        # find every c where this works.
        for i_c in range(2, len(nums), 1): # O(1000)
            i_a = 0
            i_b = i_c - 1
            while i_a != i_b and i_a < i_c and i_b >= 0: # O(1000)
                if self.triple_is_valid(nums[i_a], nums[i_b], nums[i_c]): 
                    # since we have i_a + i_b > c 
                    # AND we know i_a, ...., i_b where ... is >= i_a we also know 
                    # anything in the .... will satisfy the above condition since it will lead to a larger LHS
                    # so we can do this. 
                    ways += i_b - i_a

                    # try to decrease b 
                    i_b -= 1
                else:
                    # we need to make bigger, try increase i_a, (since i_b starts the largest it can be)
                    i_a += 1
        return ways

        
16100