Here is solution for problem “Valid Triangle Number”

1. Problem — Input / Output / Constraints

Problem: Given an array nums of non-negative integers, count the number of triplets (i, j, k) with i < j < k such that nums[i], nums[j], nums[k] can form the sides of a triangle.

Triangle inequality (for sorted sides a ≤ b ≤ c): a + b > c.

Input: nums (list of ints) Output: integer — number of valid triplets.

Example:

nums = [2,2,3,4] Output: 3

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

Constraints (typical LeetCode):

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

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

2. Intuition & Approaches

Brute force (O(N³)) Try all i < j < k and check nums[i] + nums[j] > nums[k]. Works for tiny N — too slow for N ~ 1000.

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]. For a fixed k, use two pointers left = 0, right = k-1. If nums[left] + nums[right] > nums[k] then all indices between left and right-1 with right form valid pairs (because array sorted ⇒ any nums[m] >= nums[left] for m in [left, right-1]), so add right - left to count and decrement right. Otherwise increment left.

This yields O(N²) time and O(1) extra space (besides sort).

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

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

Initialize count = 0.

We iterate k from 3 down to 2 (index):

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 = 2. Decrement right → right = 1.

Now left = 0, right = 1: 2 + 2 = 4 → not > 4. Increment left → left = 1.

left == right stop.

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

2 + 2 = 4 > 3 → valid: add right - left = 1 (pair (0,1) → [2,2,3]). count = 3. Decrement right → right = 0.

left == right stop.

Done → count = 3.

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

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

5. Correctness intuition / proof sketch

After sorting, for any fixed k and right, if nums[left] + nums[right] > nums[k], then for any m with left ≤ m < right, nums[m] >= nums[left] (since sorted), so nums[m] + nums[right] > nums[k] also. So you can count right - left valid pairs at once; moving right leftwards explores other possibilities without missing anything. The two-pointer loop enumerates all (i,j) with i<j<k exactly once in aggregated form.

6. 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) extra (or O(N) if counting sort or stable sort uses extra memory)

This is optimal for general inputs under typical constraints.

7. Variants / notes

If values are small and bounded, one can consider counting-sort style tricks, but that complicates counting triplets and rarely beats O(N²) for typical constraints.

Watch out for zeros: any triplet containing a zero cannot form a triangle unless the others are positive and satisfy a + b > c. Sorting handles zero normally.