JavaScript O(n² log n) solution using binary search


  • 0
    var triangleNumber = function(nums) {
        nums = nums.filter(a => a).sort((a, b) => a - b);
        let res = 0;
        for (let i = 0; i < nums.length - 1; i++) {
            for (let j = i + 1; j < nums.length; j++) {
                res += search(nums, nums[i] + nums[j], 0, nums.length - 1) - j - 1;
            }
        }
        return res;
    };
    
    function search(nums, target, low, high) {
        if (low > high) return low;
        let mid = low + Math.floor((high - low) / 2);
        if (target > nums[mid]) {
            return search(nums, target, mid + 1, high);
        }
        return search(nums, target, low, mid - 1);
    }
    

    This problem relies on the triangle inequality.

    See @compton_scatter's solution for speed/elegance.


Log in to reply
 

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