Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.
Example 1:
Input: nums = [2,2,3,4] Output: 3 Explanation: Valid combinations are: 2,3,4 (using the first 2) 2,3,4 (using the second 2) 2,2,3
Example 2:
Input: nums = [4,2,3,4] Output: 4
Constraints:
1 <= nums.length <= 10000 <= nums[i] <= 1000In #611 Valid Triangle Number, the task is to count how many triplets in an array can form a valid triangle. A triangle is valid when the sum of any two sides is greater than the third side. A brute force approach would check all triplets, but this leads to O(n^3) time and is inefficient for larger inputs.
A more optimal strategy begins by sorting the array. Once sorted, you can fix the largest side and use the two-pointer technique to find pairs that satisfy the triangle inequality. Because the array is ordered, when a valid pair is found, multiple combinations can be counted at once, significantly reducing checks.
Another alternative uses binary search to locate the farthest index that satisfies the triangle condition for each pair. However, the two-pointer approach is typically more efficient in practice. Sorting simplifies comparisons and enables structured traversal, resulting in a much faster solution.
This optimized approach balances readability and performance while reducing unnecessary combinations.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting + Two Pointers | O(n^2) | O(1) (excluding sort space) |
| Sorting + Binary Search | O(n^2 log n) | O(1) |
| Brute Force (Check all triplets) | O(n^3) | O(1) |
NeetCode
First, sort the array. Then, iterate through the array by selecting the third side of the triplet. Use a two-pointer technique to find valid pairs for the first and second sides. For each third side, initialize two pointers, one starting at the beginning of the list and the other just before the third side. Check the sum of the elements at the two pointers and compare it to the third side. If they form a valid triangle, move the inner pointer inward; otherwise, adjust the pointers accordingly.
Time Complexity: O(n^2), where n is the length of the input array because the main operations involve sorting and a nested loop.
Space Complexity: O(1) since it uses only a fixed amount of extra space.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
This solution sorts the array and uses nested loops; the outer loop selects the third side, and the inner loop uses two pointers to find valid pairs for the other two sides. By moving the pointers towards each other based on the condition, it efficiently finds all valid triplets.
This approach involves checking every possible triplet from the array to see if they can form a triangle by comparing their sums directly. This solution is straightforward but less efficient since it considers all combinations without optimizations such as sorting or double pointers.
Time Complexity: O(n^3), as it checks every combination of three numbers in the array.
Space Complexity: O(1), requiring minimal additional storage.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting helps enforce the triangle inequality condition efficiently. When the array is sorted, you can easily determine whether two smaller sides can form a triangle with a larger side and avoid unnecessary checks.
Yes, binary search can be used after sorting the array to find the largest valid third side for a given pair. This approach works but usually results in O(n^2 log n) complexity, which is slightly slower than the two-pointer method.
Yes, this problem is commonly discussed in coding interviews because it tests understanding of sorting, two-pointer techniques, and array traversal optimizations. Variants of the triangle inequality problem appear in interviews at major tech companies.
The optimal approach is to first sort the array and then use a two-pointer technique. By fixing the largest side and scanning the remaining elements with two pointers, you can count multiple valid combinations efficiently in O(n^2) time.
This Brute Force C solution uses three nested loops to examine every triplet and checks if they satisfy the triangle inequality condition.