Valid triangles from stick lengths

Scenario

A route planner for cyclists stores straight road segments, each with a length in metres. A planner feature looks for small loops: three segments that can close into a triangle.

Three lengths can form a triangle when the two shorter ones together are longer than the longest one. If they only equal it, the three lie flat on one line, and there is no loop. You are asked to count the sets of three segments that can form a triangle. Segments of equal length are different segments.

Your task

Write count_triangles(segments).

segments is the list of segment lengths, in no particular order. Lengths may repeat.
A triple is three different positions.
A triple can form a triangle when the sum of its two shorter lengths is strictly greater than its longest length.
Return the number of triples that can form a triangle. The answer can pass 32 bits.

Examples

Example 1 (traced)#

text2 lines

Input:  segments = [4, 6, 3, 7]
Output: 3

Sort the lengths: 3, 4, 6, 7. Fix the longest side, from the back. Then walk two pointers over the shorter lengths. If lo and hi fit, every length between them also fits with hi.

Longest	lo value	hi value	Sum of the two	What happens
7	3	6	9	greater than 7: add 2 (hi - lo), hi moves down. Count is 2
7	3	4	7	not greater than 7: lo moves up, the pointers meet
6	3	4	7	greater than 6: add 1, hi moves down. Count is 3

The longest side 4 has only one shorter length left, so it makes no triple. The answer is 3.

Example 2#

text2 lines

Input:  segments = [1, 1, 2]
Output: 0

The two shorter lengths add up to 2, which only equals the longest. The three lie flat.

Example 3#

text2 lines

Input:  segments = [5, 5, 5]
Output: 1

One triple, and 5 + 5 is greater than 5.

Constraints

1 ≤ segments.length ≤ 3,000 (segments in one region)
1 ≤ segments[i] ≤ 10^6 (metres)

What does n ≤ 3,000 tell you?

Checking every triple costs about n × n × n ÷ 6 checks. At n = 3,000 that is 4.5 × 10^9: about 45 seconds at 10^8 operations a second. Sorting and then walking two pointers for each longest side costs about n × n ÷ 2 steps, 4.5 million.

The count can reach 3,000 × 2,999 × 2,998 ÷ 6, about 4.5 × 10^9. That is beyond a 32-bit integer, so use a 64-bit type (long in Java, long long in C++).

Scenario

A route planner for cyclists stores straight road segments, each with a length in metres. A planner feature looks for small loops: three segments that can close into a triangle.

Your task

Write count_triangles(segments).

segments is the list of segment lengths, in no particular order. Lengths may repeat.
A triple is three different positions.
A triple can form a triangle when the sum of its two shorter lengths is strictly greater than its longest length.
Return the number of triples that can form a triangle. The answer can pass 32 bits.

Examples

Example 1 (traced)#

text2 lines

Input:  segments = [4, 6, 3, 7]
Output: 3

Sort the lengths: 3, 4, 6, 7. Fix the longest side, from the back. Then walk two pointers over the shorter lengths. If lo and hi fit, every length between them also fits with hi.

Longest	lo value	hi value	Sum of the two	What happens
7	3	6	9	greater than 7: add 2 (hi - lo), hi moves down. Count is 2
7	3	4	7	not greater than 7: lo moves up, the pointers meet
6	3	4	7	greater than 6: add 1, hi moves down. Count is 3

The longest side 4 has only one shorter length left, so it makes no triple. The answer is 3.

Example 2#

text2 lines

Input:  segments = [1, 1, 2]
Output: 0

The two shorter lengths add up to 2, which only equals the longest. The three lie flat.

Example 3#

text2 lines

Input:  segments = [5, 5, 5]
Output: 1

One triple, and 5 + 5 is greater than 5.

Constraints

1 ≤ segments.length ≤ 3,000 (segments in one region)
1 ≤ segments[i] ≤ 10^6 (metres)

What does n ≤ 3,000 tell you?

The count can reach 3,000 × 2,999 × 2,998 ÷ 6, about 4.5 × 10^9. That is beyond a 32-bit integer, so use a 64-bit type (long in Java, long long in C++).