Valid Triangle Number - O(N^2) log(N) Binary Search [AC]

Array     Binary Search     Binary Tree     C++     Greedy     Medium     Sorting     Two Pointers    

Problem Statement:

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

Solution:

Firstly sort nums. Now chose 1st two sides of triangle in for loop. Say a=nums[i], b=nums[j] where i<j. For the 3rd side of the triangle, check the lowest index where a+b or any number greater than that occurs in case a+b is absent. Call this index as k. Then, valid triangles can be with chosen a, b and c can be chosen from index between indices j and k.

 
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n=nums.size(), res=0;
        for (int i=0; i<n; i++)
        {
            for (int j=i+1; j<n; j++)
            {
                auto it = lower_bound(nums.begin(), nums.end(), nums[i]+nums[j]);
                int pos = it-nums.begin();
                if (pos-j-1>0) res+=(pos-j-1);
            }
        }
        return res;
    }
};