Example 1
ready- Input
nums = [ 2, 2, 3, 4 ]- Expected
3- Why
- three index triples are valid; the sides 2, 2, 4 are exactly degenerate
Valid Triangle Number
35 min · triangleNumber()mediumOpen in LeetCode #611 ↗
A pile of cut rods can offer millions of three-rod choices, yet some choices collapse flat instead of forming a triangle. You need to count only the sturdy ones.
The array nums holds non-negative side lengths. Count the index triplets
i < j < k whose three values can form a non-degenerate triangle — a triangle with
positive area rather than three points on one straight line.
For three sorted side lengths a <= b <= c, the deciding rule is strict:
a + b > c.
Keep these details straight:
- Each choice uses three different positions.
- Different index triplets count separately, even when their side values match.
- Equality isn't enough:
a + b == cmakes a flat, degenerate shape. - A zero can never belong to a valid triangle under the strict rule.
Constraints
0 <= nums.length <= 1_0000 <= nums[i] <= 1_000
Hints
Start with three loops
Enumerate every i < j < k, sort those three side lengths, and test whether the
two smaller ones add to more than the largest.
Choose the largest side first
Sort the whole array. Fix index k as the largest side, then ask how many pairs to
its left have a sum greater than nums[k].
Count a block at once
If nums[left] + nums[right] > nums[k], then every index from left through
right - 1 also forms a valid pair with right. Add right - left, then move
right inward.
Follow-up
Can you reach O(n²) time by proving when an entire block of pairs is valid, instead of checking those pairs one at a time?
Visible cases
Examples
Example 2
ready- Input
nums = [ 0, 0, 1, 1 ]- Expected
0- Why
- every three-position choice includes a zero, so none can form a triangle
Example 3
ready- Input
nums = [ 3, 4, 5 ]- Expected
1- Why
- the only three positions satisfy 3 + 4 > 5
Interview signal
Asked at
AmazonGoogleApple
Check every triple
Choose every set of three positions. Sort just those three side lengths, then apply the strict triangle rule: the two smaller sides must add to more than the largest.
def triangle_number(nums: list[int]) -> int:
count = 0
n = len(nums)
for i in range(n - 2):
for j in range(i + 1, n - 1):
for k in range(j + 1, n):
a, b, c = sorted((nums[i], nums[j], nums[k]))
if a + b > c:
count += 1
return countTime O(n³) — there are up to n choose 3 index triples. Space O(1) — sorting three values uses constant-sized storage.
Sort + count pairs
Sort nums, then fix k as the largest side. Put left at the beginning and right
just before k.
If nums[left] + nums[right] > nums[k], this pair works. More importantly, replacing
left with any position up to right - 1 only makes the first side larger, so all
right - left of those pairs work. Count that whole block and move right inward.
If the sum is too small or exactly equal, nums[left] can't work with this right —
and no smaller second side will rescue it. Move left rightward.
def triangle_number(nums: list[int]) -> int:
nums.sort()
count = 0
for k in range(len(nums) - 1, 1, -1):
left, right = 0, k - 1
while left < right:
if nums[left] + nums[right] > nums[k]:
count += right - left
right -= 1
else:
left += 1
return countTime O(n²) — each largest side gets one linear pointer scan after O(n log n) sorting. Space O(1) beyond the sorting routine's internal workspace.
The speedup comes from counting index choices in batches. Duplicate side lengths need no special handling here: equal values at different positions represent different triplets, so the block size already counts them correctly.
Loading editor
Console
ready to runReady to run.
3 cases are queued.
Visible testcase
Case 1
Expected
3
Run: visible + custom · Submit: full suite