Count the Triangles

ArraySortingTwo Pointers

Given an array of integers representing the lengths of sticks, determine how many different triangles can be formed using these sticks. To form a triangle, the sum of the lengths of any two sides must be greater than the length of the third side. Return the count of unique triangles that can be formed.

Example 1

Input

[
  2,
  2,
  3
]

Output

Explanation. A triangle can be formed with sides of length 2, 2, and 3.

Example 2

Input

[
  4,
  1,
  2
]

Output

Explanation. No triangle can be formed with sides of length 4, 1, and 2.

Example 3

Input

[
  5,
  5,
  5,
  5
]

Output

Explanation. Four identical triangles can be formed with sides of length 5.

Example 4

Input

Output

Explanation. Triangles can be formed with side lengths [10, 21, 22], [21, 22, 100], [21, 100, 101], [22, 100, 101], [100, 101, 200], [101, 200, 300].

Follow-up: Can you solve the problem in O(n^2) time complexity?

Constraints:

The input array will contain between 3 and 1000 integers, and each integer will be between 1 and 10,000.

Views: 1