Valid triangle number

Array Two Pointers Binary Search Greedy Sorting

56.7% acceptance

Feb 20, 2026

4425

257

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.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn triangle_number(mut nums: Vec<i32>) -> i32 {
    nums.sort_unstable();
    let n = nums.len();
    let mut count = 0;
    for i in (2..n).rev() {
      let mut left = 0;
      let mut right = i - 1;
      while left < right {
        if nums[left] + nums[right] > nums[i] {
          count += (right - left) as i32;
          right -= 1;
        } else {
          left += 1;
        }
      }
    }
    count
  }
}