All problems

Valid Triangle Number

Medium · two pointers

A tent maker has a pile of poles. The list sticks gives the length of each pole, and several poles may share the same length.

Three poles can be joined into a triangle with a real area when each pole is shorter than the other two poles put together. If a pole is exactly as long as the other two together, the three lie flat and do not make a triangle.

Count how many ways there are to pick three different poles that make a triangle. Two choices are different when they use different poles (different positions in the list), even if the lengths are the same. The order in which you pick the three poles does not matter.

Examples

Example 1

Input: sticks = [2, 2, 3, 4]

Output: 3

The valid choices (by position) are (2, 2, 3), (2, 3, 4) using the first 2, and (2, 3, 4) using the second 2. The choice (2, 2, 4) is flat, so it does not count.

Example 2

Input: sticks = [4, 2, 3, 4]

Output: 4

Example 3

Input: sticks = [1, 1, 2]

Output: 0

1 + 1 is exactly 2, so the poles lie flat.

Constraints