Valid Triangle Number

Q: Which edge cases should I test for Valid Triangle Number?

Zeros (a side of 0 never forms a triangle); Fewer than 3 elements.

Medium Arrays & Hashing Two Pointer Original on LeetCode

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

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.

Code

Code appears here once we start writing it.

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 Java code.

Approach	Time	Space
Brute force	`O(n³)`	`O(1)`
Optimal (sort + two pointers per largest side)	`O(n²)`	`O(1)`

1Brute force

TimeO(n³)

SpaceO(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.

Java

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;
    }
}

2Optimal (sort + two pointers per largest side)

TimeO(n²)Sort is O(n log n); each k does an O(n) two-pointer scan.

SpaceO(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++.

Java

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;
    }
}

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.

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.