Stick Triples That Form a Triangle

Medium

A box holds sticks whose lengths are listed in the array sticks. In how many ways can you pick three sticks (three different positions of the array) that can be put together into a triangle? Three lengths form a triangle when the sum of any two of them is strictly greater than the third. Sticks of equal length at different positions are different sticks, so triples with the same lengths may be counted more than once.

Example 1

sticks=[3, 5, 5, 9] → 2

(3, 5, 5) and (5, 5, 9) work. Neither (3, 5, 9) triple does, one with each 5, because 3 + 5 < 9.

Example 2

sticks=[2, 2, 2, 2] → 4

Any three sticks form an equilateral triangle, and there are 4 ways to pick three of four.

Example 3

sticks=[1, 2, 3] → 0

1 + 2 = 3 gives a flat triangle, which does not count.

Constraints

1 ≤ len(sticks) ≤ 1000
0 ≤ sticks[i] ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Two Pointers Binary Search Sorting

Similar problems

Best-Paid Gig for Each Worker Medium Mentor at Least Twice as Strong Medium Flowerbed Beauty on a Budget Hard Studios for Recording Sessions Medium Triples Under a Limit Medium

Input

sticks=[3, 5, 5, 9]

Expected

Run checks the first 3 tests in your browser. Submit checks all 116 tests on the server, hidden ones included.