611. Valid Triangle Number

At first glance, this problem looks like a simple geometry question. But in interviews, Valid Triangle Number is really about recognizing how sorting and two pointers can collapse a brute-force solution into an efficient one. Interviewers use it to test whether you can reason about constraints mathematically and then translate that reasoning into an optimized algorithm.

Problem statement

You are given an integer array nums consisting of non-negative integers. Your task is to return the total number of valid triangles that can be formed by choosing three values nums[i], nums[j], and nums[k] such that:

i < j < k

nums[i], nums[j], and nums[k] can form a valid triangle

Constraints:

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 1000

Examples

Naive approach

An easy way to solve this problem is to examine every possible triplet of side lengths and check whether it forms a valid triangle.

Logic

• Use three nested loops to generate all triplets (i, j, k) such that i < j < k.
• For each triplet, verify the triangle inequality rules:
  • nums[i] + nums[j] > nums[k]
  • nums[i] + nums[k] > nums[j]
  • nums[j] + nums[k] > nums[i]
• If all three conditions hold, increment the count.

This method directly mirrors the mathematical definition of a triangle and is easy to reason about, making it a common first instinct during interviews.

Drawback

The major limitation of this approach is performance. With three nested loops, the algorithm runs in O(n³) time. Given the constraint that nums.length can be as large as 1000, this results in hundreds of millions of checks in the worst case.

Additionally, many of these checks are redundant. The same sums are recomputed repeatedly, and no structure in the data is being exploited to prune invalid cases early. As a result, this solution will time out for large inputs and does not meet interview performance expectations.

Sorting and Two Pointers intuition

To avoid the inefficiency of checking every triplet, we restructure the problem so we can count many valid triangles at once, instead of validating them one by one.

A triangle is valid only if the sum of any two sides is strictly greater than the third side. After sorting, we can always treat the third element of a triplet as the largest side, which reduces the triangle condition to a single check: nums[i] + nums[j] > nums[k] for i < j < k

With this viewpoint, the problem becomes less about geometry and more about efficiently counting valid index triplets.

If we sort nums in nondecreasing order, we gain two key advantages:

1. The largest side is known immediately: For any triplet (i, j, k) with i < j < k, sorting guarantees: nums[i] <= nums[j] <= nums[k] so nums[k] is the largest side. That means we only need to check nums[i] + nums[j] > nums[k], the other two inequalities are automatically satisfied.
2. Pointer movements become predictable: Fix k (the largest side) and search for valid pairs (i, j) with i < j < k. Because the array is sorted:
   1. Moving i to the right increases nums[i], so the sum nums[i] + nums[j] increases.
   2. Moving j to the left decreases nums[j], so the sum decreases.

This monotonic behavior is exactly what makes the two-pointer approach work efficiently.

Step-by-step algorithm

1. Sort the array in ascending order.
2. Iterate from the end of the array and treat each element nums[k] as the largest side.
3. For each k, initialize two pointers:
   1. left = 0
   2. right = k - 1
4. While left < right:
   1. If nums[left] + nums[right] > nums[k], then all values between left and right paired with nums[right] will also form valid triangles.
      1. Add (right - left) to the result.
      2. Move right one step left.
   2. Otherwise, move left one step right to increase the sum.
5. Repeat until all possible k values are processed.

Let’s look at the following illustration to get a better understanding of the solution:

1 / 9

Code implementation

Let’s look at the code for this solution below:

def triangleNumber(nums):
    # Sort the array to apply the two-pointer technique
    nums.sort()
    n = len(nums)
    count = 0

    # Fix the largest side one by one
    for k in range(n - 1, 1, -1):
        left = 0
        right = k - 1

        while left < right:
            # Check triangle condition
            if nums[left] + nums[right] > nums[k]:
                # All pairs between left and right form valid triangles
                count += right - left
                right -= 1
            else:
                left += 1

    return count


def main():
    testCases = [
        [3, 4, 6, 7],
        [1, 2, 2, 3],
        [5, 10, 12, 13, 15],
        [2, 3, 4, 8],
        [6, 7, 9, 10, 12]
    ]

    for i, nums in enumerate(testCases, 1):
        print(i, ".  Input nums = ", nums, sep="")
        print("    Number of valid triangles: ", triangleNumber(nums), sep="")
        print("-" * 75)


if __name__ == "__main__":
    main()

Why this works

Sorting gives us control over how sums change as pointers move. Increasing the left pointer increases the total sum, while decreasing the right pointer reduces it. This monotonic behavior guarantees that once the triangle condition is met, it holds for an entire range of values.

Instead of validating each triplet independently, the algorithm counts valid ranges, which is the core optimization that reduces the time complexity.

Time complexity

• Sorting the array takes O(n log n) time.
• For each element treated as the largest side, we perform a two-pointer scan over the remaining elements, which takes O(n) time.
• As this scan is repeated for up to n elements, the overall time complexity is dominated by O(n²).

Space complexity

• The algorithm uses a constant amount of extra space for pointers and counters.
• No additional data structures are required.
• Sorting is performed in place, so aside from the input array, the space usage remains constant.

This makes the solution both time-efficient and space-optimal within the given constraints. Therefore, the space complexity of the solution is O(1).

Common pitfalls and interview tips

1. Forgetting to sort the array: The two-pointer logic relies entirely on sorted data. Without sorting, pointer movement no longer guarantees that sums increase or decrease predictably, and the approach breaks down.
2. Checking all three triangle inequalities: Once the array is sorted, only i + j > k needs to be checked. Verifying the other two conditions is unnecessary and signals a lack of optimization awareness.
3. Counting one triangle at a time: A frequent mistake is incrementing the count by one when the condition is met. When nums[left] + nums[right] > nums[k], all values between left and right form valid triangles with nums[k]. Failing to count the full range leads to undercounting and misses the core optimization.
4. Ignoring zeros and small values: Zero-length sides cannot form a triangle, but no special handling is required. After sorting, such values naturally fail the inequality and are skipped by the algorithm.