Valid Triangle Number

In one line

Sort the sides, fix the largest each round, and let the gap between two pointers count every valid pair at once.

time O(n^2)space O(1)

Given an array of positive side lengths, count how many triplets can form a valid triangle. A triangle is valid when the sum of its two shorter sides is greater than the longest one. Checked naively, that's three inequalities per triple, so $O(n^3)$ overall.

Sorting collapses that down to one check per triple. Once a ≤ b ≤ c, proving a + b > c is enough, since c is already the largest and the other two inequalities hold automatically. The two-pointer trick goes further, turning that one check into a bulk count instead of one triplet at a time.

Why fixing the largest side works

Count a whole range in one step

With the largest side c fixed and left ≤ right scanning everything smaller, suppose nums[left] + nums[right] > c. Then every index between left and right - 1 also sums past c when paired with right, since sorted order guarantees it.
That's right - left valid triplets counted in $O(1)$ work, not one comparison per triplet.
After counting, shrink right: it's been paired with every smaller value that could possibly work.

What the shortcut does not do

a + b > c only proves a triangle once the array is sorted and c is confirmed the largest; applied to an arbitrary triple it proves nothing.
It only produces a count, not which sides were used: like 3Sum, the original positions aren't part of the answer.
It assumes positive lengths; zero or negative values break the geometry the inequality depends on, not just the arithmetic.

Signals in the problem statement

"triangle" or "form a triangle" alongside a list of side lengths
counting every valid triplet, not just finding one
positive integers as input
comparing a sum of two sides against the third

The pattern

1Sort the array ascending.
2
Fix the largest side at index k, walking inward from the end.
3
Two-pointer the range before k: sum too big → add right - left to the count and shrink right.
4Sum too small → grow left. Repeat for the next k.

@itsnas triangle.ts

codetriangle.ts

function triangleNumber(nums: number[]): number {
  nums.sort((a, b) => a - b)
  let count = 0
 
  for (let k = nums.length - 1; k >= 2; k--) {
    let left = 0
    let right = k - 1
 
    while (left < right) {
      if (nums[left] + nums[right] > nums[k]) {
        count += right - left // every pair from left..right-1 works
        right--
      } else {
        left++ // nums[left] is too small for this right
      }
    }
  }
 
  return count
}

main

Nas (@itsnas)

fn triangle_number(mut nums: Vec<i32>) -> i32 {
    nums.sort();
    let mut count = 0;
 
    for k in (2..nums.len()).rev() {
        let (mut left, mut right) = (0usize, k - 1);
 
        while left < right {
            if nums[left] + nums[right] > nums[k] {
                count += (right - left) as i32;
                right -= 1;
            } else {
                left += 1;
            }
        }
    }
 
    count
}

main

Nas (@itsnas)

int triangleNumber(std::vector<int>& nums) {
  std::sort(nums.begin(), nums.end());
  int count = 0;
 
  for (int k = nums.size() - 1; k >= 2; k--) {
    int left = 0, right = k - 1;
 
    while (left < right) {
      if (nums[left] + nums[right] > nums[k]) {
        count += right - left;
        right--;
      } else {
        left++;
      }
    }
  }
 
  return count;
}

main

Nas (@itsnas)

func triangleNumber(nums []int) int {
	sort.Ints(nums)
	count := 0
 
	for k := len(nums) - 1; k >= 2; k-- {
		left, right := 0, k-1
 
		for left < right {
			if nums[left]+nums[right] > nums[k] {
				count += right - left // every pair from left..right-1 works
				right--
			} else {
				left++ // nums[left] is too small for this right
			}
		}
	}
 
	return count
}

main

Nas (@itsnas)

def triangle_number(nums: list[int]) -> int:
    nums.sort()
    count = 0
 
    for k in range(len(nums) - 1, 1, -1):
        left, right = 0, k - 1
 
        while left < right:
            if nums[left] + nums[right] > nums[k]:
                count += right - left  # every pair from left..right-1 works
                right -= 1
            else:
                left += 1  # nums[left] is too small for this right
 
    return count

main

Nas (@itsnas)

Complexity

Time

O (n^{2})

An O(n) two-pointer sweep runs once per fixed largest side, dominating the O(n log n) sort.

Space

O (1)

Auxiliary space only, excludes the sort's internal use.

Common pitfalls

1
Checking all three inequalities
Once the array is sorted and c is the fixed largest side, checking a + c > b and b + c > a too is redundant, and if the array isn't sorted first, checking only one inequality is wrong.
2
Counting one triplet at a time
Incrementing the count by one and moving right by one on every hit throws away the bulk-count insight and degrades to $O(n^3)$ .
3
Letting the sweep touch the fixed index
The inner two pointers must stay strictly inside [0, k - 1]: reaching k itself compares the fixed side against a copy of itself.
4
Not shrinking after a hit
Every value from left to right - 1 is already counted against the current right: staying on the same right recounts the same range on the next iteration.

Variants worth knowing

1
3Sum: the same fix-one-and-two-pointer-the-rest shape, but proving an exact equality instead of counting a bulk range.
2
Container With Most Water: the same "sum exceeds a bound, so a whole side can be discarded" logic, but tracking the single best answer instead of a running count.
3
3Sum Smaller: counts triples under a target sum using the identical bulk-range trick, just without the triangle-specific largest-side fix.

Practice, easiest first

Valid Triangle NumberMedium

3Sum SmallerMedium

3SumMedium

Container With Most WaterMedium

Valid Triangle Number

Why fixing the largest side works

The pattern

Complexity

Common pitfalls

Variants worth knowing

Practice, easiest first

What's next in the notebook?

3Sum

Two Sum II

Container With Most Water

Two Pointers