Valid Triangle Number
Valid Triangle Number is a medium arrays & hashing problem solved with the two pointer pattern.
The best approach, optimal (sort + two pointers per largest side), runs in O(n²) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force up.
Problem
Given an array of side lengths nums, count the triplets of indices whose values can form a triangle. Three lengths form a triangle when the sum of any two is greater than the third.
Examples
Example 1
- Input
nums = [3, 4, 4, 6]- Output
4- Why
- (3,4,4), (3,4,6) twice (either 4), and (4,4,6).
Example 2
- Input
nums = [1, 1, 5]- Output
0
Constraints
1 <= nums.length <= 10000 <= nums[i] <= 1000
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n³) | O(1) |
| Optimal (sort + two pointers per largest side) | O(n²) | O(1) |
1Brute force
O(n³)O(1)Sort, then check every triplet i < j < k with nums[i] + nums[j] > nums[k].
- Sort the array.
- Three nested loops; count triplets passing the check.
class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int count = 0, n = nums.length;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
for (int k = j + 1; k < n; k++)
if (nums[i] + nums[j] > nums[k]) count++;
return count;
}
}class Solution:
def triangleNumber(self, nums: List[int]) -> int:
nums.sort()
count, n = 0, len(nums)
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if nums[i] + nums[j] > nums[k]:
count += 1
return countclass Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int count = 0, n = nums.size();
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
for (int k = j + 1; k < n; k++)
if (nums[i] + nums[j] > nums[k]) count++;
return count;
}
};function triangleNumber(nums) {
nums.sort((a, b) => a - b);
let count = 0;
const n = nums.length;
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++)
for (let k = j + 1; k < n; k++)
if (nums[i] + nums[j] > nums[k]) count++;
return count;
}2Optimal (sort + two pointers per largest side)
O(n²)Sort is O(n log n); each k does an O(n) two-pointer scan.O(1)Fix k as the largest side. With lo = 0 and hi = k - 1: if nums[lo] + nums[hi] > nums[k], every index from lo to hi - 1 also works with hi, so add hi - lo and move hi down. Otherwise lo is too small, so move it up.
- Sort nums.
- For k from n - 1 down to 2, set lo = 0, hi = k - 1.
- If nums[lo] + nums[hi] > nums[k]: count += hi - lo, hi--.
- Else lo++.
class Solution {
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int count = 0;
for (int k = nums.length - 1; k >= 2; k--) {
int lo = 0, hi = k - 1;
while (lo < hi) {
if (nums[lo] + nums[hi] > nums[k]) {
count += hi - lo;
hi--;
} else {
lo++;
}
}
}
return count;
}
}class Solution:
def triangleNumber(self, nums: List[int]) -> int:
nums.sort()
count = 0
for k in range(len(nums) - 1, 1, -1):
lo, hi = 0, k - 1
while lo < hi:
if nums[lo] + nums[hi] > nums[k]:
count += hi - lo
hi -= 1
else:
lo += 1
return countclass Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(), nums.end());
int count = 0;
for (int k = nums.size() - 1; k >= 2; k--) {
int lo = 0, hi = k - 1;
while (lo < hi) {
if (nums[lo] + nums[hi] > nums[k]) {
count += hi - lo;
hi--;
} else {
lo++;
}
}
}
return count;
}
};function triangleNumber(nums) {
nums.sort((a, b) => a - b);
let count = 0;
for (let k = nums.length - 1; k >= 2; k--) {
let lo = 0, hi = k - 1;
while (lo < hi) {
if (nums[lo] + nums[hi] > nums[k]) {
count += hi - lo;
hi--;
} else {
lo++;
}
}
}
return count;
}Edge cases to test
- Zeros (a side of 0 never forms a triangle)
- Fewer than 3 elements
Hints
Hint 1
After sorting, a <= b <= c form a triangle exactly when a + b > c.
Hint 2
Fix the largest side c, then count pairs with two pointers.
FAQ
What is the best time complexity for Valid Triangle Number?
Optimal (sort + two pointers per largest side) runs in O(n²) time and O(1) extra space. Sort is O(n log n); each k does an O(n) two-pointer scan.
Which pattern does Valid Triangle Number use?
It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Container With Most Water, Trapping Rain Water.
Is there a brute force solution for Valid Triangle Number?
Yes. Brute force takes O(n³) time and O(1) space. Sort, then check every triplet i < j < k with nums[i] + nums[j] nums[k].
Which edge cases should I test for Valid Triangle Number?
Zeros (a side of 0 never forms a triangle); Fewer than 3 elements.