Two Pointers
Triangle Numbers
medium
Count: 10
DESCRIPTION (inspired by Leetcode.com)
Write a function to count the number of triplets in an integer array nums 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.
The triplets do not need to be unique.
Example:
Input:
nums = [11,4,9,6,15,18]
Output:
10
Explanation: Valid combinations are...
4, 15, 18 6, 15, 18 9, 15, 18 11, 15, 18 9, 11, 18 6, 11, 15 9, 11, 15 4, 9, 11 6, 9, 11 4, 6, 9
Solution
Visualization
Python
Try these examples:
def triangleNumber(nums):nums.sort()count = 0for i in range(len(nums) - 1, 1, -1):left = 0right = i - 1while left < right:if nums[left] + nums[right] > nums[i]:count += right - leftright -= 1else:left += 1return count
valid triangle numbers
0 / 26
Explanation
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
Python
def triangleNumber(nums):nums.sort()count = 0for i in range(len(nums) - 1, 1, -1):left = 0right = i - 1while left < right:if nums[left] + nums[right] > nums[i]:count += right - leftright -= 1else:left += 1return count
valid triangle numbers
0 / 5
When nums[left] + nums[right] < nums[i], we know that all triplets between left and right are also invalid, so we increment left to look for a larger smallest value.
Visualization
Python
def triangleNumber(nums):nums.sort()count = 0for i in range(len(nums) - 1, 1, -1):left = 0right = i - 1while left < right:if nums[left] + nums[right] > nums[i]:count += right - leftright -= 1else:left += 1return 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
Python
def triangleNumber(nums):nums.sort()count = 0for i in range(len(nums) - 1, 1, -1):left = 0right = i - 1while left < right:if nums[left] + nums[right] > nums[i]:count += right - leftright -= 1else:left += 1return count
Count: 4
move left pointer
0 / 20
Mark as read
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.