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).
This approach is a refinement of the brute-force method. By first sorting the array, we can simplify the triangle inequality check. If the side lengths a, b, c are sorted such that a <= b <= c, we only need to check if a + b > c.
Algorithm
- First, sort the input array
numsin non-decreasing order. - Initialize a counter
countto 0. - Use three nested loops to iterate through triplets
(i, j, k)withi < j < k. - Since the array is sorted,
nums[i] <= nums[j] <= nums[k]. We only need to check the conditionnums[i] + nums[j] > nums[k]. - If the condition is met, we have found a valid triangle, so we increment
count. - An optional optimization: if
nums[i] + nums[j] <= nums[k], we can break the innermost loop (overk) because any subsequent elementnums[k'](wherek' > k) will also not satisfy the condition. - Return
countafter all loops complete.
Walkthrough
The key insight here is that for three sorted side lengths a <= b <= c, the conditions a + c > b and b + c > a are always true (assuming positive lengths). Thus, the triangle inequality check reduces to a single condition: a + b > c.
The algorithm starts by sorting the nums array. Then, it proceeds with three nested loops to pick triplets (nums[i], nums[j], nums[k]) with i < j < k. Because the array is sorted, we are guaranteed that nums[i] <= nums[j] <= nums[k]. Inside the innermost loop, we just check if nums[i] + nums[j] > nums[k]. If it is, we increment our count. This reduces the number of comparisons inside the loop, but the overall number of triplets to check remains the same, leading to a cubic time complexity.
import java.util.Arrays; class Solution { public int triangleNumber(int[] nums) { Arrays.sort(nums); int count = 0; int n = nums.length; for (int i = 0; i < n - 2; i++) { if (nums[i] == 0) continue; // Optimization for zero-length sides for (int j = i + 1; j < n - 1; j++) { for (int k = j + 1; k < n; k++) { if (nums[i] + nums[j] > nums[k]) { count++; } else { // If it fails for this k, it will fail for all subsequent k's break; } } } } return count; }}Complexity
Time
O(N^3). Sorting takes O(N log N), but it is dominated by the three nested loops, which run in O(N^3) time.
Space
O(log N) or O(N), depending on the space complexity of the sorting algorithm used. For instance, Java's `Arrays.sort` for primitives uses a Dual-Pivot Quicksort which takes O(log N) space on average.
Trade-offs
Pros
Slightly more optimized than the naive brute-force due to a simpler check.
The logic inside the loops is cleaner.
Cons
The time complexity is still O(N^3) in the worst case, which is too slow for large inputs.
Requires modifying the input array by sorting it, or using extra space for a sorted copy.
The most efficient solution involves sorting the array and then using a two-pointer technique. By fixing the largest side of the potential triangle, we can efficiently find the number of valid pairs for the other two sides in linear time, leading to an overall quadratic time complexity.
Algorithm
- Sort the input array
nums. - Initialize a counter
countto 0. - Iterate backwards through the array with an index
kfromn-1down to2.nums[k]will be considered as the largest sidecof a potential triangle. - For each
k, use two pointers,left = 0andright = k - 1, to find pairs(a, b)in the subarraynums[0...k-1]. - While
left < right:- If
nums[left] + nums[right] > nums[k], a valid triangle is formed. Since the array is sorted,nums[right]paired with any element fromnums[left]tonums[right-1]will also form a valid triangle withnums[k]. There areright - leftsuch pairs. Add this number tocountand decrementrightto check for pairs with a smaller second side. - If
nums[left] + nums[right] <= nums[k], the sum is too small. Incrementleftto try and find a larger sum.
- If
- Return the total
count.
Walkthrough
This approach significantly improves performance by reducing the search space. After sorting the array nums, we iterate from the end of the array to fix the largest side of the triangle, c = nums[k]. For each c, we need to find the number of pairs (a, b) from the subarray nums[0...k-1] such that a + b > c.
This subproblem is solved efficiently using two pointers, left starting at 0 and right at k-1.
- If
nums[left] + nums[right] > nums[k], we have found a valid pair. Crucially, any elementnums[i]whereleft <= i < rightwill also satisfynums[i] + nums[right] > nums[k]becausenums[i] >= nums[left]. This means we have foundright - leftvalid triangles. We add this to our count and decrementrightto see if a smallerbcan also form a triangle. - If
nums[left] + nums[right] <= nums[k], the sum is too small. To increase the sum, we must use a largera, so we incrementleft. This process continues untilleftandrightcross. Since the two-pointer scan takes O(k) time for eachk, the total time complexity is O(N^2).
import java.util.Arrays; class Solution { public int triangleNumber(int[] nums) { int n = nums.length; if (n < 3) { return 0; } Arrays.sort(nums); int count = 0; for (int k = n - 1; k >= 2; k--) { int left = 0; int right = k - 1; while (left < right) { if (nums[left] + nums[right] > nums[k]) { count += (right - left); right--; } else { left++; } } } return count; }}Complexity
Time
O(N^2). Sorting takes O(N log N). The nested loop structure with the two-pointer scan takes O(N^2), which dominates the overall complexity.
Space
O(log N) or O(N), for the space used by the sorting algorithm.
Trade-offs
Pros
Highly efficient with a quadratic time complexity.
This is the optimal approach for the given constraints.
Cons
The logic is more complex than the brute-force approaches.
Requires sorting, which alters the original array or needs extra space.
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; }}class Solution: def triangleNumber(self, nums: List[int]) -> int: nums . sort() ans, n = 0, len(nums) for i in range(n - 2): for j in range(i + 1, n - 1): k = bisect_left(nums, nums[i] + nums[j], lo=j + 1) - 1 ans += k - j return ansclass Solution { public: int triangleNumber ( vector < int >& nums ) { sort ( nums . begin (), nums . end ()); int ans = 0 , n = nums . size (); for ( int i = 0 ; i < n - 2 ; ++ i ) { for ( int j = i + 1 ; j < n - 1 ; ++ j ) { int k = lower_bound ( nums . begin () + j + 1 , nums . end (), nums [ i ] + nums [ j ]) - nums . begin () - 1 ; ans += k - j ; } } return ans ; } };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.