Valid Triangle Number

Medium
356.

Valid Triangle Number

Valid Triangle Number is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and Meta interviews.

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 <= 30
  • 0 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var triangleNumber = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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 <= 30
  • 0 <= nums[i] <= 1000

Hints for Valid Triangle Number

  1. Hint 1

    Sort the array; then only the condition a + b > c for the largest side c needs checking.

  2. Hint 2

    Fix the largest side and run two pointers over the prefix below it.

  3. Hint 3

    When nums[i] + nums[j] > nums[k], every index between i and j also works with j — add j - i at 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

  1. Sort ascending.
  2. For k from the end down to 2: i = 0, j = k - 1; if a[i] + a[j] > a[k], add j - i and decrement j; else increment i.

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 count

Java

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