611

611. Valid Triangle Number (Medium)

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

Companies:
Bloomberg, LinkedIn, ByteDance

Related Topics:
Array, Two Pointers, Binary Search, Greedy, Sorting

Similar Questions:

• 3Sum Smaller (Medium)

Solution 1. Binary Search

The naive solution is of O(N^3) time complexity, that is, for each triplet, detect if it can form a triangle. This solution will get TLE.

To optimize it, we first sort nums in ascending order. And for each pair a and b, use binary search to find the count of numbers greater than a + b and less than b - a (b >= a).

// OJ: https://leetcode.com/problems/valid-triangle-number
// Author: github.com/lzl124631x
// Time: O(N^2logN)
// Space: O(1)
class Solution {
public:
    int triangleNumber(vector<int>& A) {
        int N = A.size(), ans = 0;
        sort(begin(A), end(A));
        for (int i = 0; i < N; ++i) {
            int a = A[i];
            for (int j = i + 1; j < N; ++j) {
                int b = A[j];
                auto begin = upper_bound(A.begin() + j + 1, A.end(), b - a); 
                auto end = lower_bound(A.begin() + j + 1, A.end(), a + b);
                ans += max(0, (int)(end - begin));
            }
        }
        return ans;
    }
};