611. Valid Triangle Number

Description

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

 

Solutions

Solution: Two Pointers

• Time complexity: O(n²)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
const triangleNumber = function (nums) {
  const n = nums.length;
  let result = 0;

  nums.sort((a, b) => a - b);

  for (let index = n - 1; index > 1; index--) {
    const num = nums[index];
    let left = 0;
    let right = index - 1;

    while (left < right) {
      if (nums[left] + nums[right] > num) {
        result += right - left;
        right -= 1;
      } else {
        left += 1;
      }
    }
  }

  return result;
};