Given an array consists of non-negative integers, your task is to count 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: [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


Note:

The length of the given array won't exceed 1000.

The integers in the given array are in the range of [0, 1000].


Let's start with the algorithm,


const triangleNumber = nums  => {

  // Count of triangles

    let count = 0;


 

    // The three loops select three

    // different values from array

    for (let i = 0; i < nums.length; i++)

    {

        for (let j = i + 1; j < nums.length; j++)

        {

 

            // The innermost loop checks for

            // the triangle property

          for (let k = j + 1; k < nums.length; k++)

 

              // Sum of two sides is greater

              // than the third

              if (nums[i] + nums[j] > nums[k] && nums[i] + nums[k] > nums[j] && nums[k] + nums[j] > nums[i])

              {

                  count++;

              }

        }

    }

    return count;

}


console.log(triangleNumber([2,2,3,4]));



Here we are using the brute force method, to run three loops and keep track of the number of triangles possible so far. The three loops select three different values from an array. The innermost loop checks for the triangle property which specifies the sum of any two sides must be greater than the value of the third side).


Given steps to solve the problem:

  • Run three nested loops each loop starting from the index of the previous loop to the end of the array i.e run first loop from 0 to n, loop j from i to n, and k from j to n
  • Check if array[i] + array[j] > array[k], i.e. sum of two sides is greater than the third
  • Check condition 2 for all combinations of sides by interchanging i, j, k
  • If all three conditions match, then increase the count
  • Print the count

I hope you understood the algorithm, if you have any doubts let us know in the comments.