Valid Triangle Number - Solution & Explanation
Problem Statement
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] <= 1000
Approach Overview
Problem Overview: You are given an integer array where each value represents a potential side length. The task is to count how many triplets (i, j, k) can form a valid triangle. A triangle is valid only if the triangle inequality holds: the sum of any two sides must be greater than the third side.
Approach 1: Brute Force (O(n^3) time, O(1) space)
The straightforward way is to check every possible triplet. Iterate three nested loops and pick indices i, j, and k. For each combination, verify the triangle inequality conditions: a + b > c, a + c > b, and b + c > a. If all conditions hold, increment the count. This approach works but becomes slow for large inputs because it evaluates every triplet explicitly. It’s useful for understanding the constraint logic but rarely acceptable in interviews due to the cubic runtime.
Approach 2: Sorting + Two-Pointer Technique (O(n^2) time, O(1) space)
The key optimization comes from sorting the array first. Once sorted, you only need to check one inequality: nums[left] + nums[right] > nums[k]. Fix the largest side at index k, then use two pointers (left and right) scanning the prefix of the array. If the sum of the two smaller sides is greater than nums[k], then every element between left and right with right forms a valid triangle, so you add right - left to the count and move right leftward. Otherwise move left forward. Sorting combined with the two pointers pattern reduces the search dramatically and runs in quadratic time.
Approach 3: Sorting + Binary Search (O(n^2 log n) time, O(1) space)
Another optimization after sorting is to fix two sides i and j, then use binary search to find the largest index k such that nums[i] + nums[j] > nums[k]. All indices between j+1 and k form valid triangles with the chosen pair. This reduces the third loop to a logarithmic lookup. The method is slightly slower than the two-pointer approach but still far better than brute force.
Both optimized solutions rely on sorting, a common pattern when solving array problems involving order-based constraints. Sorting allows you to reason about the triangle inequality with fewer checks.
Recommended for interviews: The sorting + two-pointer solution is what most interviewers expect. It shows that you recognize the triangle inequality optimization and can apply the two-pointer pattern effectively. Explaining the brute force approach first demonstrates problem understanding, then improving it to the O(n^2) solution shows strong algorithmic thinking.
Approach 1: Two-Pointer Technique
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.
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.
Complexity
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.
Approach 2: Brute Force Approach
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.
Complexity
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 3: Sorting + Binary Search
A valid triangle must satisfy: the sum of any two sides is greater than the third side. That is:
$a + b \gt c \tag{1}
a + c \gt b \tag{2}
b + c \gt a \tag{3}
If we arrange the sides in ascending order, i.e., a leq b leq c, then obviously conditions (2) and (3) are satisfied. We only need to ensure that condition (1) is also satisfied to form a valid triangle.
We enumerate i in the range [0, n - 3], enumerate j in the range [i + 1, n - 2], and perform binary search in the range [j + 1, n - 1] to find the first index left that is greater than or equal to nums[i] + nums[j]. Then, the values of k in the range [j + 1, left - 1] satisfy the condition, and we add them to the result ans.
The time complexity is O(n^2log n), and the space complexity is O(log n), where n$ is the length of the array.
Complexity Comparison
| 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. |
| Sorting + Binary Search | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force (Triple Loop) | O(n^3) | O(1) | Good for understanding triangle inequality or validating small inputs |
| Sorting + Binary Search | O(n^2 log n) | O(1) | When you want a clear improvement over brute force with predictable searches |
| Sorting + Two Pointers | O(n^2) | O(1) | Best approach for interviews and large arrays |
Video Solution
Valid Triangle Number | Leetcode 611 | Live Coding session 🔺🔺🔺 • Coding Decoded • 14,558 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Valid Triangle Number easy or hard?
Valid Triangle Number Python/Java solution
How to solve Valid Triangle Number in O(n^2)?
What is the best approach for Valid Triangle Number?
Is Valid Triangle Number asked at Google/Amazon/Meta?
What data structure is used in Valid Triangle Number?
What is the time complexity of Valid Triangle Number?
Ready to solve this problem?
Practice Valid Triangle Number with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor