c++ short code O(n^2) time and O(1) space solution


  • 0
    A

    The algorithm asks to enumerate all triplets without duplicates, therefore it is always good to sort the array first. Then we enumerate (a, b, c) with a <= b <= c and c < a + b. To do this, we can try a and b as a double for loop, then to find the number of possible c, we can find the first element nums[idx] such that nums[idx] >= a + b. An ordinary way to do this is to use binary search as the array is already sorted. But we can do better if we observe that b is also in the increasing order to be enumerated. If we find idx such that nums[idx] >= a + b, then when we enumerate next possible b' >= b, we can start our pointer from idx to find the first element nums[idx'] > a + b'. The inner while loop iterate at most O(n) time during the inner for loop.

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

Log in to reply
 

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