# C++ O(N^2logN) solution

• 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, I first sort `nums` in ascending order. And for each doublet `a` and `b`, use binary search to find the count of numbers greater than `a + b` and less than `a - b (a >= b)`.

``````// OJ: https://leetcode.com/problems/valid-triangle-number
// Auther: github.com/lzl124631x
// Time: O(N^2logN)
// Space: O(1)
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int cnt = 0, N = nums.size();
for (int i = 0; i < N; ++i) {
for (int j = i + 1; j < N; ++j) {
int lb = nums[j] - nums[i], rb = nums[i] + nums[j];
int L = j + 1, R = N - 1, left = 0;
while (L <= R) {
int M = (L + R) / 2;
if (nums[M] > lb) R = M - 1;
else L = M + 1;
}
left = L;
L = j + 1, R = N - 1;
while (L <= R) {
int M = (L + R) / 2;
if (nums[M] >= rb) R = M - 1;
else L = M + 1;
}
if (R >= left) cnt += R - left + 1;
}
}
return cnt;
}
};
``````

Or use the built-in functions `lower_bound` and `upper_bound`.

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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.