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] <= 1000First, 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.
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.
C++
Java
Python
C#
JavaScript
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.
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.
This Brute Force C solution uses three nested loops to examine every triplet and checks if they satisfy the triangle inequality condition.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^3), as it checks every combination of three numbers in the array.
Space Complexity: O(1), requiring minimal additional storage.
| Approach | Complexity |
|---|---|
| Two-Pointer Technique | Time Complexity: O(n^2), where n is the length of the input array because the main operations involve sorting and a nested loop. |
| Brute Force Approach | Time Complexity: O(n^3), as it checks every combination of three numbers in the array. |
Triangle - Dynamic Programming made Easy - Leetcode 120 • NeetCode • 56,666 views views
Watch 9 more video solutions →Practice Valid Triangle Number with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor