LeetCode 611 - Valid Triangle Number

The problem asks us to determine how many triplets from a given integer array nums can form a valid triangle. In geometric terms, a triangle is valid if the sum of any two sides is greater than the third side.

leetcodemediumarraytwo-pointersbinary-searchgreedysorting

LeetCode Problem 611

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Binary Search, Greedy, Sorting

Solution

Problem Understanding

The problem asks us to determine how many triplets from a given integer array nums can form a valid triangle. In geometric terms, a triangle is valid if the sum of any two sides is greater than the third side. Because we are only concerned with side lengths from an array, the key condition is that for three numbers a, b, and c (where a <= b <= c), the triangle inequality reduces to a + b > c.

The input nums is an array of integers representing potential side lengths, and the output is a single integer: the count of distinct triplets that satisfy the triangle inequality.

The constraints tell us that the array has at most 1000 elements, and the numbers are non-negative integers up to 1000. This suggests that a naive triple-loop solution (O(n^3)) may be too slow for the worst case, but approaches that reduce the number of comparisons will work efficiently.

Important edge cases include arrays with zeros, arrays where all numbers are equal, arrays with fewer than three numbers, and arrays where no combination can form a triangle.

Approaches

The brute-force approach is straightforward: iterate over all possible triplets (i, j, k) and check whether the three numbers satisfy the triangle inequality. This guarantees correctness because it exhaustively checks every combination, but the time complexity is O(n^3), which will be slow for n = 1000.

The optimal approach leverages sorting. After sorting nums, we can fix the largest side nums[k] and use two pointers i and j to find valid pairs (nums[i], nums[j]) such that nums[i] + nums[j] > nums[k]. The key insight is that once nums[i] + nums[j] > nums[k], all pairs between i and j satisfy the condition due to the sorted order. This reduces the time complexity to O(n^2) and is efficient enough for the constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Iterate over all triplets, check triangle inequality
Optimal O(n^2) O(1) Sort array and use two pointers to count valid pairs efficiently

Algorithm Walkthrough

  1. Sort the array nums in ascending order. This ensures that for any triplet (nums[i], nums[j], nums[k]) with i < j < k, nums[i] <= nums[j] <= nums[k].
  2. Initialize a variable count to 0. This will hold the total number of valid triangles.
  3. Iterate k from len(nums) - 1 down to 2, treating nums[k] as the largest side of the triangle.
  4. For each k, initialize two pointers: i = 0 and j = k - 1.
  5. While i < j, check if nums[i] + nums[j] > nums[k].
  • If true, all pairs (i, i+1, ..., j-1) combined with j and k form valid triangles. Increment count by j - i and decrement j by 1 to consider the next smaller second side.
  • If false, increment i by 1 to increase the sum and try again.
  1. Continue until i >= j, then move to the next k.
  2. Return count.

Why it works: Sorting ensures that as the sum of the two smaller sides increases, all intermediate pairs between i and j satisfy the triangle inequality. This invariant allows us to count multiple valid triangles in one step without checking each explicitly.

Python Solution

from typing import List

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        count = 0
        n = len(nums)
        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

The Python implementation first sorts the array and initializes count to accumulate valid triangles. It iterates over potential largest sides and uses a two-pointer approach to efficiently find the number of valid triangles for each fixed largest side. Incrementing count by j - i avoids explicitly checking all smaller combinations, exploiting the sorted order to guarantee correctness.

Go Solution

import "sort"

func triangleNumber(nums []int) int {
    sort.Ints(nums)
    count := 0
    n := len(nums)
    for k := n - 1; k >= 2; k-- {
        i, j := 0, k - 1
        for i < j {
            if nums[i] + nums[j] > nums[k] {
                count += j - i
                j--
            } else {
                i++
            }
        }
    }
    return count
}

In Go, sorting is done via sort.Ints. The two-pointer technique works the same as in Python. Go handles slices naturally, so no additional data structures are needed. Integer overflow is not an issue because nums[i] and nums[j] are bounded by 1000.

Worked Examples

Example 1: nums = [2,2,3,4]

  1. Sorted: [2,2,3,4]
  2. k = 3 (nums[k] = 4), i=0, j=2
  • nums[i]+nums[j]=2+3=5>4 → count += 2 → j=1
  • nums[i]+nums[j]=2+2=4 not > 4 → i=1
  • i=j → move to next k
  1. k=2 (nums[k]=3), i=0, j=1
  • nums[i]+nums[j]=2+2=4>3 → count += 1 → j=0
  • i>=j → done
  1. Total count = 3

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

  1. Sorted: [2,3,4,4]
  2. k=3 (nums[k]=4), i=0, j=2
  • nums[i]+nums[j]=2+4=6>4 → count += 2 → j=1
  • nums[i]+nums[j]=2+3=5>4 → count +=1 → j=0
  1. k=2 (nums[k]=4), i=0, j=1
  • nums[i]+nums[j]=2+3=5>4 → count +=1 → j=0
  1. Total count = 4

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) Sorting takes O(n log n), and the two-pointer scan for each largest side takes O(n), resulting in O(n^2) overall.
Space O(1) No extra data structures beyond variables; sorting in-place is O(1) space.

The two-pointer approach avoids the O(n^3) brute-force iterations while still counting all valid triangles by leveraging the sorted order.

Test Cases

# Provided examples
assert Solution().triangleNumber([2,2,3,4]) == 3  # Example 1
assert Solution().triangleNumber([4,2,3,4]) == 4  # Example 2

# Edge and boundary cases
assert Solution().triangleNumber([]) == 0  # empty array
assert Solution().triangleNumber([0,0,0]) == 0  # all zeros
assert Solution().triangleNumber([1,1,1]) == 1  # minimum non-zero triangle
assert Solution().triangleNumber([3,4,5,6,10]) == 6  # multiple triangles
assert Solution().triangleNumber([1]*1000) == 166167000  # large array with same numbers
Test Why
[] Tests empty input handling
[0,0,0] Tests zeros cannot form a triangle
[1,1,1] Tests minimal valid triangle
[3,4,5,6,10] Checks general multiple triangles
[1]*1000 Stress test with large input size, all equal elements

Edge Cases

One important edge case is when the array contains zeros. A zero cannot form a triangle with any other side, so the algorithm correctly ignores such cases because the sum of any two positive numbers must be greater than zero, but if a side is zero, the triangle inequality fails.

Another edge case is arrays with fewer than three elements. Since a triangle requires three sides, the algorithm will naturally return zero because the outer loop starts from index n-1 down to 2. If n < 3, the loop does not execute.

A third edge case is arrays where all numbers are equal. Here, the triangle inequality holds for any triplet. The algorithm efficiently counts all combinations without repeated explicit checks, and the sorted array ensures that the two-pointer counting method correctly captures all valid triangles.