Valid Triangle Number — Solution in Python, Java & C++
Valid Triangle Number solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Valid Triangle Number is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Binary Search, Two Pointers
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an integer array nums, return the number of index triples that can form a triangle with non-zero area using the values at those indices as side lengths.
Example 1
Input: nums = [2,2,3,4]
Output: 3
Explanation: The valid triples are (2,3,4), (2,3,4) using the other 2, and (2,2,3).
Example 2
Input: nums = [4,2,3,4]
Output: 4
Example 3
Input: nums = [0,0,0]
Output: 0
Constraints
3 <= nums.length <= 300 <= nums[i] <= 1000
Hints for Valid Triangle Number
Hint 1
Sort the array; then only the condition
a + b > cfor the largest sidecneeds checking.Hint 2
Fix the largest side and run two pointers over the prefix below it.
Hint 3
When
nums[i] + nums[j] > nums[k], every index betweeniandjalso works withj— addj - iat once.
How to solve Valid Triangle Number
Sort; fix the largest side k and run two pointers over the prefix: when a[i] + a[j] > a[k], all indices between i and j also work with j, adding j - i at once.
Approach
- Sort ascending.
- For
kfrom the end down to 2:i = 0,j = k - 1; ifa[i] + a[j] > a[k], addj - iand decrementj; else incrementi.
Why it works
With the largest side fixed, only a + b > c needs checking. If a[i] + a[j] exceeds a[k], so does a[i'] + a[j] for every i' > i, which is the batch count; otherwise a[i] is too small for this j and every smaller j.
Complexity
- Time —
O(n²) - Space —
O(1) beyond the sort
Pitfalls
- Zero-length sides can never form a triangle; the strict inequality excludes them automatically.
Reference solution
Python
def triangleNumber(nums) -> int:
ordered = sorted(nums)
count = 0
for k in range(len(ordered) - 1, 1, -1):
i, j = 0, k - 1
while i < j:
if ordered[i] + ordered[j] > ordered[k]:
count += j - i
j -= 1
else:
i += 1
return countJava
public static int triangleNumber(int[] nums) {
int[] s = nums.clone();
Arrays.sort(s);
int count = 0;
for (int k = s.length - 1; k >= 2; k--) {
int i = 0, j = k - 1;
while (i < j) {
if (s[i] + s[j] > s[k]) {
count += j - i;
j--;
} else {
i++;
}
}
}
return count;
}C++
int triangleNumber(vector<int>& nums) {
vector<int> s = nums;
sort(s.begin(), s.end());
int count = 0;
for (int k = (int) s.size() - 1; k >= 2; k--) {
int i = 0, j = k - 1;
while (i < j) {
if (s[i] + s[j] > s[k]) {
count += j - i;
j--;
} else {
i++;
}
}
}
return count;
}JavaScript
var triangleNumber = function(nums) {
const sorted = nums.slice().sort(function(a, b) { return a - b; });
let count = 0;
for (let k = sorted.length - 1; k >= 2; k--) {
let i = 0, j = k - 1;
while (i < j) {
if (sorted[i] + sorted[j] > sorted[k]) {
count += j - i;
j--;
} else {
i++;
}
}
}
return count;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms