Here is solution for problem “Valid Triangle Number”

1. Input, Output. Constraints

1. Input: nums (list of ints)

nums = [2,2,3,4]

1. Output:

Valid triplets (by values): [2,2,3], [2,3,4] (with two choices for the 2s) → total 3

1. Constraints (typical LeetCode):

• 1 <= len(nums) <= 1000 (so O(N²) feasible)

• 0 <= nums[i] <= 10^6 (values may be large)

2. Intuition & Approaches

1. Brute force (O(N³))

• Try all i < j < k and check nums[i] + nums[j] > nums[k]

1. Better (O(N²)) — sort + two pointers

• Sort the array ascending. Fix the largest side c = nums[k] (iterate k from end toward 2).

• Then find pairs (i, j) with i < j < k such that nums[i] + nums[j] > nums[k] => nums[i] + nums[k] > nums[k] > nums[j] and nums[j] + nums[k] > nums[i] of course.

3. Dry run (two-pointer) — example nums = [2,2,3,4]

Sort: already [2,2,3,4].

=> k = 3 → c = 4. Set left = 0, right = 2.

nums[left] + nums[right] = 2 + 3 = 5 > 4 → valid: add right - left = 2. (pairs: (0,2),(1,2) → sides [2,3,4] twice)

=> Count: right - left + 1

4. Implementations

A — Brute force (clear, O(N³)) — for small N / illustration

def valid_triangle_number_bruteforce(nums):
    n = len(nums)
    count = 0
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                a, b, c = nums[i], nums[j], nums[k] # we only need check triangle inequalities; easiest is to sort
                x, y, z = sorted((a, b, c))
                if x + y > z:
                    count += 1
    return count

B — Optimal: sort + two pointers (O(N²))

def valid_triangle_number(nums):
    n = len(nums)
    if n < 3:
        return 0

    nums.sort()
    count = 0

    # fix k as the largest side index
    for k in range(n - 1, 1, -1):  # k from n-1 down to 2
        left, right = 0, k - 1
        while left < right:
            if nums[left] + nums[right] > nums[k]:
                # For this right, any index in [left, right-1] with right forms valid pair
                count += (right - left)
                right -= 1
            else:
                left += 1

    return count

print(valid_triangle_number([2,2,3,4])) # prints 3

5. Complexity

• Sorting: O(N log N)

• Two-pointer nested loop: worst-case O(N²) (each k does up to O(k) work)

• Space: O(1)