Valid Triangle Number: Sort, Fix, Two Pointers

LeetCode 611, Valid Triangle Number, asks you to count how many triplets from an array can form a valid triangle. The triangle inequality rule is the core constraint: the sum of any two sides must be strictly greater than the third side. Once you sort the array and fix the largest side, the problem collapses into a two-pointer counting exercise that runs in O(n^2) time.

The problem

Given an array of non-negative integers nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths.

Three sides a, b, c (where a is less than or equal to b is less than or equal to c) form a valid triangle when a + b > c. After sorting, you only need to check this one condition because a + c > b and b + c > a are automatically satisfied when c is the largest.

The approach

The brute force checks all O(n^3) triplets. That is too slow for arrays up to 1000 elements. Here is the O(n^2) strategy:

1. Sort the array. This lets you fix the largest side and reason about the other two.
2. Fix the largest side at index c, iterating from right to left (from n-1 down to 2).
3. Use two pointers lo = 0 and hi = c - 1 on the subarray to the left of c.
4. If nums[lo] + nums[hi] > nums[c], then every index between lo and hi also works as the left side (because the array is sorted, and increasing the left side only increases the sum). That means all hi - lo pairs with hi as the second side are valid. Add hi - lo to the count and move hi left.
5. If nums[lo] + nums[hi] is not greater than nums[c], the sum is too small. Move lo right to increase it.

This is the same two-pointer convergence pattern you see in 3Sum and 3Sum Closest, but instead of looking for a specific sum, you are counting how many pairs exceed a threshold.

def triangle_number(nums):
    nums.sort()
    n = len(nums)
    count = 0

    for c in range(n - 1, 1, -1):
        lo, hi = 0, c - 1

        while lo < hi:
            if nums[lo] + nums[hi] > nums[c]:
                count += hi - lo
                hi -= 1
            else:
                lo += 1

    return count

Step-by-step walkthrough

Let's trace through nums = [2, 2, 3, 4] (already sorted). The blue pointer is c (fixed largest side), amber is lo, and green is hi.

The algorithm finds all three valid triangles: (2, 3, 4) at indices (0, 2, 3), (2, 3, 4) at indices (1, 2, 3), and (2, 2, 3) at indices (0, 1, 2). Each time nums[lo] + nums[hi] > nums[c], the batch count hi - lo captures every valid pairing in one shot.

Complexity analysis

Time: O(n^2). Sorting takes O(n log n). The outer loop runs n - 2 times, and for each iteration the two pointers perform at most O(n) work. Total: O(n log n) + O(n^2) = O(n^2).

Space: O(1) extra. The sort is in-place and only a few variables are used. Some languages use O(log n) stack space for the sort, but no auxiliary data structures are needed.

Edge cases

• Zeros in the array. A side length of 0 can never form a valid triangle because 0 + b is never strictly greater than c when c is at least as large as b. The two-pointer logic handles this naturally since nums[lo] + nums[hi] will not exceed nums[c] when one of the values is 0.
• All identical elements. For example, [3, 3, 3, 3]. Every triplet is valid because 3 + 3 > 3. The algorithm counts C(4, 3) = 4 triplets correctly.
• Array with fewer than 3 elements. The outer loop does not execute and the count stays at 0, which is correct.
• Array with many duplicates. The two-pointer approach handles duplicates without any special skip logic. Duplicates are separate entries, and each triplet is counted independently.

The building blocks

1. Fix-one-and-scan

This is the same skeleton used in 3Sum, 3Sum Closest, and 4Sum. Fix one element (here the largest side), then solve a simpler two-variable subproblem on the remaining subarray. Sorting is always the prerequisite because it lets the two pointers move monotonically.

for c in range(n - 1, 1, -1):
    lo, hi = 0, c - 1
    # two-pointer scan on nums[0..c-1]

2. Two-pointer batch counting

Instead of checking individual pairs, you count entire ranges at once. When nums[lo] + nums[hi] > threshold, you know that nums[lo+1] + nums[hi], nums[lo+2] + nums[hi], and so on are also above the threshold. So you add hi - lo in one step. This batch technique is what brings the inner loop from O(n^2) down to O(n) per fixed element.

3. The triangle inequality

For sorted sides a, b, c, you only need to check a + b > c. The other two inequalities are guaranteed because c is the largest. This simplification is what makes the two-pointer approach possible. Without sorting, you would need to check all three conditions for every triplet.

From understanding to recall

Valid Triangle Number is a clean application of the fix-one-and-scan pattern combined with batch counting. The algorithm is short, but the reasoning behind the batch step is the part that fades first. Why does count += hi - lo work? Because sorting guarantees that every value between lo and hi is at least as large as nums[lo], so if nums[lo] + nums[hi] > nums[c], then replacing lo with any larger index only increases the sum.

Drill the two-pointer batch counting idea on its own. Once that building block is solid, you can reassemble the full solution for Valid Triangle Number, 3Sum, and related problems without re-deriving the logic each time.

Related posts

• 3Sum Closest - Same fix-one-and-scan skeleton with two converging pointers on a sorted array
• 3Sum - The classic triplet problem that uses the same sorting and two-pointer foundation
• Container With Most Water - Another two-pointer convergence problem where the decision rule determines which pointer moves