Valid Triangle Number

main.md

Question

Approach

I solve this by first sorting the array. For each possible largest side nums[k], I use two pointers (i at start, j just before k) to count valid triangles. If nums[i] + nums[j] > nums[k], then all pairs from i to j-1 with j and k are valid, so I add (j - i) to the count and move j left. Otherwise, I move i right.

Implementation

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        count = 0
        
        for k in range(n - 1, 1, -1):
            i, j = 0, k - 1
            while i < j:
                if nums[i] + nums[j] > nums[k]:
                    count += (j - i)
                    j -= 1
                else:
                    i += 1
        return count

Complexities

• Time: O(n^2)
• Space: O(1)