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 and $O(n^3)$ overall.

Sorting collapses that down to one check per triple: once a ≤ b ≤ c, proving a + b > c is enough — the other two inequalities hold automatically, since c is already the largest. The two-pointer trick then goes further, turning that one check into a bulk count rather than a single 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, if nums[left] + nums[right] > c then every index between left and right - 1 also sums past c when paired with right — 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-number.ts

codetriangle-number.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
}

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
}

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

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
}

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

Naseebullah

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

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.

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)$ .

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.

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.