Write a function to count the number of triplets in an array nums of non-negative integers that could form the sides of a triangle.
For three sides to form a valid triangle, all three of these conditions must hold: (a + b > c), (a + c > b), and (b + c > a), where (a), (b), and (c) are the side lengths. In other words, the sum of every possible pair must exceed the third side.
For three sides to form a valid triangle, all three of these conditions must be true:
(a + b > c)
(a + c > b)
(b + c > a)
where (a), (b), and (c) are the three side lengths. This means the sum of every possible pair of sides must exceed the remaining side. For example, sides [1, 2, 1000] do NOT form a valid triangle because while (2 + 1000 > 1), the condition (1 + 2 > 1000) fails. By sorting the array, we can leverage the two-pointer technique to count all valid triplets in O(n2) time and O(1) space.
The key to this question is realizing that if we sort three numbers from smallest to largest (say a ≤ b ≤ c), we only need to check if a + b > c. If this condition holds, the other two conditions (a + c > b and b + c > a) are automatically satisfied because c ≥ b and b ≥ a. For example, with 4, 8, 9, if 4 + 8 > 9 is true, then we have a valid triplet.
But not only that, every number between 4 and 8 also forms a valid triplet when paired with 8 and 9. Since the array is sorted and 4 + 8 > 9, replacing 4 with any larger value (5, 6, 7, or 8) will still satisfy the condition — so all of these are valid triplets too.
This means that if we sort the input array, and then iterate from the end of the array to the beginning, we can use the two-pointer technique to efficiently count all valid triplets.
The pointers i, left, and right represent the current triplet we are considering. If nums[left] + nums[right] > nums[i], then every index from left to right - 1 also forms a valid triplet with right and i — because the array is sorted, so each of those values is at least as large as nums[left]. That gives us right - left valid triplets in one step. We then decrement right to look for valid triplets with a smaller middle value.
Visualization
def triangleNumber(nums):
nums.sort()
count = 0
for i in range(len(nums) - 1, 1, -1):
left = 0
right = i - 1
while left < right:
if nums[left] + nums[right] > nums[i]:
count += right - left
right -= 1
else:
left += 1
return count
valid triangle numbers
0 / 5
When nums[left] + nums[right] < nums[i], we know that every triplet using nums[left] as its smallest side is also invalid, because pairing it with any value up to nums[right] only gives a smaller sum. So we increment left to look for a larger smallest value.
Visualization
def triangleNumber(nums):
nums.sort()
count = 0
for i in range(len(nums) - 1, 1, -1):
left = 0
right = i - 1
while left < right:
if nums[left] + nums[right] > nums[i]:
count += right - left
right -= 1
else:
left += 1
return count
Count: 4
move right pointer
0 / 1
Each time left and right cross, we decrement i and reset left and right to their positions at opposite ends of the array. This happens until i is less than 2, at which point we have counted all valid triplets.
Visualization
def triangleNumber(nums):
nums.sort()
count = 0
for i in range(len(nums) - 1, 1, -1):
left = 0
right = i - 1
while left < right:
if nums[left] + nums[right] > nums[i]:
count += right - left
right -= 1
else:
left += 1
return count
Count: 4
move left pointer
0 / 20
Complexity
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n²) where n is the length of the input array. Sorting costs O(n log n), but the counting step dominates: the outer loop fixes each of the n values as the largest side, and for each one the left and right pointers sweep the array in O(n). That gives O(n²) overall.
Space Complexity: O(1) we only keep a running count and the i, left, and right indices, so we use constant extra space beyond sorting the array in place.
Your account is free and you can post anonymously if you choose.