Faangprep Logo
Log inStart free
Browse curriculum

Valid Triangle Number

Count how many triples of values from the integer array nums could be the three side lengths of a valid triangle.

MediumSolve on LeetCode

Examples

Input:nums = [2,2,3,4]
Output:3
Explain:

Valid combinations are:

  1. 2,3,4 (using the first 2)
  2. 2,3,4 (using the second 2)
  3. 2,2,3
Input:nums = [4,2,3,4]
Output:4
Explain:

Valid combinations are:

  1. 2,3,4 (first 4)
  2. 2,3,4 (second 4)
  3. 2,4,4
  4. 3,4,4

Problem Understanding

We need to find triplets (a, b, c) such that they can form a valid triangle.

Triangle Inequality Theorem:
For three lengths to form a triangle, the sum of any two sides must be greater than the third side:

  • a + b > c
  • a + c > b
  • b + c > a

Simplification:
If we sort the numbers such that a <= b <= c, we strictly know that a + c > b and b + c > a (since c is the largest). The only condition we need to check is:

a + b > c

Algorithm Strategy

This problem is a variation of 3-Sum. We fix the longest side c (let's say nums[k]) and try to find two smaller sides a (nums[i]) and b (nums[j]) such that nums[i] + nums[j] > nums[k].

Algorithm:

  1. Sort the array in non-decreasing order.
  2. Iterate k from the end (n-1 down to 2). This sets our longest side c.
  3. Initialize i = 0 and j = k - 1.
  4. Two Pointer Check:
    • If nums[i] + nums[j] > nums[k]: Valid! Since the array is sorted, every number from nums[i] to nums[j-1] summed with nums[j] will ALSO be greater than nums[k]. This gives us j - i valid triangles. We count them and move j left (j--) to look for more.
    • If nums[i] + nums[j] <= nums[k]: The sum is too small. We need a larger smallest side, so we move i right (i++).

Interactive Visualization

We fix k (longest side) and count pairs (i, j) where nums[i] + nums[j] > nums[k].

Dry Run: nums = [2, 2, 3, 4] (Sorted)

k Index/Val i Index/Val j Index/Val Check (i+j > k) Action Count
3 / 4 0 / 2 2 / 3 2+3=5 > 4 (YES) Add (j-i)=2, j-- 2
3 / 4 0 / 2 1 / 2 2+2=4 !> 4 (NO) Too small, i++ 2
3 / 4 1 / 2 1 / 2 i meets j Next k 2
2 / 3 0 / 2 1 / 2 2+2=4 > 3 (YES) Add (j-i)=1, j-- 3

Edge Cases & Common Mistakes

Edge Cases:

  • Array Length < 3: Cannot form any triangle. Return 0.
  • Zeroes: Side lengths must be positive. 0, 0, 0 is not a valid triangle.

Common Mistakes:

  • Forgetting to Sort: The greedy logic strictly depends on a <= b <= c.
  • Wrong Loop Direction: We must iterate k backwards (largest to smallest) to fix c as the largest side.
  • Integer Overflow: The sum of two large integers might overflow. In languages like C++/Java, be careful with nums[i] + nums[j].

Solution

Valid Triangle Number Code
1var triangleNumber = function(nums) {
2    nums.sort((a, b) => a - b);
3    let count = 0;
4    
5    for (let k = nums.length - 1; k >= 2; k--) {
6        let i = 0;
7        let j = k - 1;
8        while (i < j) {
9            if (nums[i] + nums[j] > nums[k]) {
10                count += j - i;
11                j--;
12            } else {
13                i++;
14            }
15        }
16    }
17    return count;
18};
Previous

3-Sum

Next

Move Zeroes

The approach, step by step

  1. Sort

    Sort the side lengths in non-decreasing order.

  2. Fix the longest side

    For k from the last index down to 2, set i = 0 and j = k - 1.

  3. Count pairs

    If nums[i] + nums[j] > nums[k], add j - i and move j in; otherwise move i up.

Frequently asked questions

Why is a + b > c the only check needed after sorting?

With a ≤ b ≤ c, a + c > b and b + c > a hold automatically because c is the largest side. Only the two shorter sides need to exceed the longest.

Why can a single valid pair add j - i triangles at once?

If nums[i] + nums[j] > nums[k], every index from i up to j - 1 holds a value at least nums[i], so each of them also works with nums[j]. All j - i of those pairs are counted before j moves.

What is the time complexity of Valid Triangle Number?

O(n²): sorting costs O(n log n) and, for each longest side k, the two pointers cross at most k positions.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description