Valid Triangle Number
MedPrompt
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,3Example 2:
Input: nums = [4,2,3,4]
Output: 4
Constraints:
1 <= nums.length <= 10000 <= nums[i] <= 1000
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to check every possible triplet of numbers from the array and verify if they can form a valid triangle. This involves iterating through all combinations of three elements and applying the triangle inequality theorem.
Algorithm
- Initialize a counter
countto 0. - Use three nested loops to select three distinct indices
i,j, andkfrom the array, such thati < j < k. - Let the side lengths be
a = nums[i],b = nums[j], andc = nums[k]. - For each triplet, check if it satisfies all three conditions of the triangle inequality theorem:
a + b > c,a + c > b, andb + c > a. - If all conditions are met, increment the
count. - After checking all possible triplets, return
count.
Walkthrough
This method uses three nested loops to generate all unique triplets (nums[i], nums[j], nums[k]) from the input array. For each triplet, we must verify that it can form a triangle. According to the triangle inequality theorem, the sum of the lengths of any two sides of a triangle must be greater than the length of the third side. Therefore, for a triplet (a, b, c) to be valid, it must satisfy a + b > c, a + c > b, and b + c > a. We maintain a counter, which is incremented for every triplet that satisfies these three conditions. While simple, this approach is very slow because it checks a number of triplets proportional to N cubed.
class Solution { public int triangleNumber(int[] nums) { int count = 0; int n = nums.length; for (int i = 0; i < n - 2; i++) { for (int j = i + 1; j < n - 1; j++) { for (int k = j + 1; k < n; k++) { if (nums[i] + nums[j] > nums[k] && nums[i] + nums[k] > nums[j] && nums[j] + nums[k] > nums[i]) { count++; } } } } return count; }}Complexity
Time
O(N^3), where N is the number of elements in `nums`. The three nested loops result in a cubic number of checks.
Space
O(1) extra space, as we only use a few variables to store indices and the count.
Trade-offs
Pros
Simple to understand and implement.
Does not require any modification to the input array.
Cons
Extremely inefficient due to its cubic time complexity.
Likely to cause a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints (N up to 1000).
Solutions
Solution
class Solution {public int triangleNumber(int[] nums) { Arrays.sort(nums); int n = nums.length; int res = 0; for (int i = n - 1; i >= 2; --i) { int l = 0, r = i - 1; while (l < r) { if (nums[l] + nums[r] > nums[i]) { res += r - l; --r; } else { ++l; } } } return res; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.