Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

For sorted nonnegative sides a <= b <= c, a nondegenerate triangle exists exactly when a + b > c. Fixing the largest side leaves a sorted pair-search problem. If the smallest candidate works with a chosen middle side, every larger candidate before that middle side works too.

Approach

Sort the array and choose each index k as the largest side.
Set i = 0 and j = k - 1. If nums[i] + nums[j] > nums[k], count all j - i pairs ending at j, then decrease j.
Otherwise, increase i: this smallest candidate cannot work with the current j or any smaller one.
Stop when the pointers meet and sum over all k. The strict inequality excludes flat triangles and automatically rules out zero-length sides. Equal values at different indices still represent distinct choices.

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        res = 0

        for k in range(n - 1, 1, -1):
            j = k - 1
            i = 0
            while i < j:
                if nums[i] + nums[j] > nums[k]:
                    res += j - i
                    j -= 1
                else:
                    i += 1

        return res

Complexity analysis

For n numbers, sorting costs O(n log n) and the fixed-third-side two-pointer scans cost O(n²), so total time is O(n²). Auxiliary space is O(1) for the scan, while the language's in-place sort may use up to O(n) implementation space.