Show problems as
Classic problem #611MediumArrayTwo PointersBinary SearchGreedySorting

Valid Triangle Number

Real-world version: Bracing Strut Triples
Tracked in this browser only
Read Valid Triangle Number on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A workshop has a pile of steel struts; nums[i] is the length of the strut in slot i, and a length of 0 marks a slot holding an offcut that is too short to use. The struts arrive in no particular order.

Three struts can be bolted into a rigid triangular brace exactly when each of their lengths is strictly less than the sum of the other two, which is what gives the brace a positive area. A flat, collapsed arrangement does not count.

Count the triples of slots (i, j, k) with i < j < k whose three struts form a rigid brace. Struts of equal length in different slots are different struts, so each triple of slots is counted separately.

Examples

Example 1

Input
nums = [6, 3, 4, 6]
Output
4

All four triples of slots qualify: 6, 3, 4 has every length under the sum of the other two, and so do 6, 3, 6 and 6, 4, 6 and 3, 4, 6.

Example 2

Input
nums = [2, 3, 5]
Output
0

The only triple has 2 + 3 equal to 5, so the arrangement is flat rather than rigid and nothing is counted.

Example 3

Input
nums = [0, 1, 1]
Output
0

Slot 0 holds an offcut of length 0, and 0 + 1 does not exceed 1, so the only triple fails.

Constraints

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000
  • With at most 1000 struts the count never exceeds 166167000.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def triangle_number(nums: list[int]) -> int:
Java
public int triangleNumber(int[] nums)

More on the same topics