C++ O(N^2logN) solution


  • 0

    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;
      }
    };
    

Log in to reply
 

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