Valid Triangle Number

Three lengths make a triangle when the two shorter sides together are longer than the longest one. Lengths 2, 3 and 4 work (2 + 3 > 4); 2, 3 and 6 don't (the two short sides can't reach across).

Checked naively, that's three inequalities for each of $O(n^3)$ triples. Sorting cuts it to one: once a ≤ b ≤ c, a + b > c is the only check that can fail, because c is already the biggest.

One comparison, many triangles

Sort, and fix the largest side c. Now put two pointers on the smaller values: L at the start, R just below c.

Index 0: 2 (L)
Index 1: 3 (✓)
Index 2: 4 (✓)
Index 3: 5 (✓)
Index 4: 6 (R)
Index 5: 7 (c)

c = 7. 2 + 6 = 8 beats it. Every value between L and R is at least 2, so 3 + 6, 4 + 6 and 5 + 6 beat it too: four triangles from one comparison.

2 + 6 > 7, and 2 is the smallest value in play. Swap it for any value between L and R and the sum only grows, so all of them pair with 6 too. That's R - L = 4 triangles counted in one step. Then 6 has been paired with everything that could work, so move R in.

When the sum is too small, the opposite holds: L is too short to reach c even with the largest partner, so move L up.

L	R	Sum vs 7	Count	Move
2	6	8, beats	+4	R in
2	5	7, ties		L up
3	5	8, beats	+2	R in
3	4	7, ties		L up, pointers meet

Six triangles with 7 as the longest side. Then fix c = 6 and repeat on the values before it.

Counting one at a time (count++, move R by one) throws the batch away and slides back to $O(n^3)$ . And keep the pointers strictly below c's index, or c gets compared with itself.

Counting R − L at a time

@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)

$O(n^2)$ time: one $O(n)$ sweep per fixed side, which outweighs the sort. $O(1)$ extra space.

This is 3Sum's fix-one-then-sweep shape with one twist: fixing the largest value instead of the smallest is what turns a single hit into a range you can count. The same trick solves 3Sum Smaller, which counts triples under a target.

Valid Triangle NumberMedium

3Sum SmallerMedium

3SumMedium

Container With Most WaterMedium

Valid Triangle Number

One comparison, many triangles

Counting R − L at a time

The Two Egg Drop Problem: Why the Answer Is 14

Invert This Binary Tree (For a CRUD Job)

3Sum

Two Sum II