What is the Valid Triangle Number pattern?

The Valid Triangle Number is a common coding interview pattern in Two Pointers problems. It provides a structured approach to solving related algorithm challenges efficiently.

When should I use Valid Triangle Number?

Use the Valid Triangle Number pattern when you encounter problems matching its characteristics. Check the "When to Use" and "Clues" sections in the lesson for specific indicators.

Is Valid Triangle Number asked in FAANG interviews?

Yes, Valid Triangle Number is an essential pattern commonly tested in FAANG and top tech company technical interviews.

Two Pointers

Medium

Valid Triangle Number

Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

10 min read

Solve on LeetCode

Examples

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

Output:3

Explain:

Valid combinations are:

2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3

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

Output:4

Explain:

Valid combinations are:

2,3,4 (first 4)
2,3,4 (second 4)
2,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:

Sort the array in non-decreasing order.
Iterate k from the end (n-1 down to 2). This sets our longest side c.
Initialize i = 0 and j = k - 1.
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

Step 1 / 5

i (a)

j (b)

k (c)

Sorted: [2, 2, 3, 4]. Fix k=3 (val 4). i=0 (val 2), j=2 (val 3). Check: 2 + 3 > 4? YES (5 > 4).

Custom Input

See the Logic in Motion

Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.

Unlock VisualizerPREMIUM FEATURE

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep