# [LeetCode 611. Valid Triangle Number](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/610/week-3-july-15th-july-21st/3815/)
### Daily challenge Jul 15, 2021 (MEDIAN)

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

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

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

:::warning
**Constraints:**
* 1 <= nums.length <= 1000
* 0 <= nums[i] <= 1000
:::

---

### Approach 1 : Brute Force :bulb:
**`TLE`** **`O(n^3)`**

將 **`nums`** 排序， 使用三層 for loop 遍歷所有可能。
若 **`nums[j] + nums[k] = nums[i]`**，則找到一個答案。

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        // brute force --> TLE //
        sort(nums.begin(), nums.end());
        
        int count = 0;
        for(int i=nums.size()-1; i>=2; i--){
            for(int j=i-1; j>=1; j--){
                for(int k=j-1; k>=0; k--){
                    if(nums[j] + nums[k] > nums[i]) count++;
                }
            }
        }
        
        return count;
    }
};

### Approach 2 : Optimize Brute Force :bulb:
**`116 ms`** **`O(n^2)`**

既然已經將 **`nums`** `由小到大`排序過，我們就不需要檢查所有可能。

我們需要做的是先固定 *`(i, j)`*，找到 *`k`* 符合 **`num[i] + num[j] > num[k]`** 的`右極限`，此時 **`count += k - j - 1`** ( -1 因為 k^th^ 不符 )。

下一步，我們移動 *`j + 1`*，但是我們不須將 *`k`* 重製到 *`j + 1`*，因為 *`(j+1, k-1)`* 之間的可能都是符合的 (當 *`i`*、*`k`* 固定，且 *`nums[j] <= nums[j+1]`*，所有符合 *`nums[j]`* 的答案一定也符合 *`nums[j+1]`*)，這樣可以剩下大量的多餘計算。

:::spoiler SEE MORE
>Initial state --->
>* i = 0
>* j = i + 1
>* k = i + 2
>
| 2 | 5 | 6 | 6 | 6 | 8 | 9 |NULL |
| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| i | j | k

>When *nums[k] = 8* ---> invalid
>
| 2 | 5 | 6 | 6 | 6 | 8 | 9 |NULL|
| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| i | j | | | | k | |

>Next state ---> **we don't need to reset k to j+1**
>
| 2 | 5 | 6 | 6 | 6 | 8 | 9 |NULL|
| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| i | | j | | | k |
:::

---

class Solution {
public:
    int triangleNumber(vector<int>& nums) {    
        // optimize
        int size = nums.size();
        int count = 0;
        
        sort(nums.begin(), nums.end());
        for(int i=0; i<size-2; i++){
            if(nums[i] == 0)    continue;
            
            int k = i + 2;
            for(int j=i+1; j<size-1; j++){
                while(k < size && nums[i] + nums[j] > nums[k])  k++;
                
                count += k - j - 1; // -1 becauce nums[k] is not the answer
            }
        }
        
        return count;
    }
};

### Approach 3 : MUCH FASTER (Use two pointer) :book:
**`84 ms`** **`O(n^2)`**

與 Approach 2 想法相同，但只使用一層迴圈以及兩個指標 ( left & right )。

>* If **`num[left] + num[right] > num[i]`** ---> **`count = right - left`**, and we can check other *smaller sum* ---> **`right - 1`**.
>* Otherwise, we have to a find *bigger sum* ---> **`left + 1`**.

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        // much faster
        int count = 0;
        sort(nums.begin(), nums.end());
        
        for(int i = nums.size()-1; i>=2; i--){
            int left = 0, right = i-1;
            
            while(left < right){
                if(nums[left] + nums[right] > nums[i]){
                    count += right - left;
                    right--;
                }
                else    left++;
            }
        }
        
        return count;
    }
};