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
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.
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.
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.
Mark as read
Your account is free and you can post anonymously if you choose.