Problem Description

You are given an integer array nums. Your task is to find how many combinations of three numbers from this array can form a valid triangle.

For three sides to form a valid triangle, they must satisfy the triangle inequality theorem: the sum of any two sides must be greater than the third side. Specifically, if we have three sides a, b, and c, they can form a triangle if and only if:

• a + b > c
• a + c > b
• b + c > a

You need to count all possible triplets (groups of three numbers) from the array that satisfy this condition. The same element at different positions can be part of different triplets, but you cannot use the same array element multiple times within a single triplet.

For example, if nums = [2, 2, 3, 4], the valid triplets that can form triangles are:

• (2, 3, 4) at indices (0, 2, 3)
• (2, 3, 4) at indices (1, 2, 3)
• (2, 2, 3) at indices (0, 1, 2)

So the answer would be 3.

The solution sorts the array first, then for each pair of sides, uses binary search to find how many third sides can form a valid triangle with them. When the array is sorted and we fix two smaller sides nums[i] and nums[j] where i < j, we only need to check the condition nums[i] + nums[j] > nums[k] for the third side, as the other two conditions are automatically satisfied due to the sorted order.

Intuition

The key insight is that checking all three triangle inequality conditions can be simplified. When we sort the array, if we pick three sides where a ≤ b ≤ c, we only need to verify one condition: a + b > c. The other two conditions (a + c > b and b + c > a) are automatically satisfied because c is the largest side.

Think about it this way: if c is the largest side and a + b > c, then:

• a + c must be greater than b (since c ≥ b)
• b + c must be greater than a (since both b and c are at least as large as a)

This observation leads us to sort the array first. Once sorted, we can fix two sides and efficiently find all valid third sides.

For any pair of sides nums[i] and nums[j] where i < j, we need to find all positions k where k > j and nums[i] + nums[j] > nums[k]. Since the array is sorted, all valid k values form a continuous range. The largest valid k is the position just before nums[k] becomes greater than or equal to nums[i] + nums[j].

This is where binary search becomes useful. We can use bisect_left to find the first position where nums[k] >= nums[i] + nums[j]. The position just before this (minus 1) gives us the last valid index for the third side. The count of valid triangles with sides at positions i and j is then k - j, representing all positions from j + 1 to k.

By iterating through all possible pairs (i, j) and using binary search to count valid third sides, we efficiently count all triangles without checking every single triplet combination, reducing the time complexity from O(n³) to O(n² log n).

Learn more about Greedy, Two Pointers, Binary Search and Sorting patterns.

Solution Approach

The implementation follows a systematic approach using sorting and binary search:

1. Sort the array: First, we sort nums in ascending order. This allows us to leverage the property that for sorted sides a ≤ b ≤ c, we only need to check if a + b > c.

2. Fix two sides with nested loops: We use two nested loops to fix the first two sides:

   • The outer loop iterates i from 0 to n - 2 (where n is the array length)
   • The inner loop iterates j from i + 1 to n - 1
   • This ensures we pick two distinct elements where nums[i] ≤ nums[j]

3. Find valid third sides using binary search: For each pair (nums[i], nums[j]), we need to find all valid third sides nums[k] where:

   • k > j (to avoid reusing elements)
   • nums[i] + nums[j] > nums[k] (triangle inequality)

   The code uses bisect_left(nums, nums[i] + nums[j], lo=j + 1) to find the first position where nums[k] >= nums[i] + nums[j]. The parameters are:

   • nums: the sorted array to search in
   • nums[i] + nums[j]: the target sum we're searching for
   • lo=j + 1: start searching from position j + 1 onwards

4. Count valid triangles: The expression k = bisect_left(...) - 1 gives us the last valid index where nums[k] < nums[i] + nums[j]. The number of valid third sides is k - j, which represents all positions from j + 1 to k inclusive.

5. Accumulate the result: We add k - j to our answer for each valid pair (i, j) and return the total count.

The algorithm efficiently counts all valid triangles with time complexity O(n² log n) - O(n²) for the two nested loops and O(log n) for each binary search operation.

Example Walkthrough

Let's walk through the solution with nums = [4, 2, 3, 2].

Step 1: Sort the array After sorting: nums = [2, 2, 3, 4]

Step 2: Iterate through pairs of sides

Iteration 1: i=0, j=1 (sides: 2, 2)

• We have nums[0] = 2 and nums[1] = 2
• Sum = 2 + 2 = 4
• Use binary search starting from position j+1=2 to find where value ≥ 4 would be inserted
• bisect_left([2, 2, 3, 4], 4, lo=2) returns index 3
• k = 3 - 1 = 2
• Valid third sides are at positions from j+1=2 to k=2, which is just position 2 (value 3)
• Count: k - j = 2 - 1 = 1
• This forms triangle (2, 2, 3)

Iteration 2: i=0, j=2 (sides: 2, 3)

• We have nums[0] = 2 and nums[2] = 3
• Sum = 2 + 3 = 5
• Use binary search starting from position j+1=3 to find where value ≥ 5 would be inserted
• bisect_left([2, 2, 3, 4], 5, lo=3) returns index 4 (end of array)
• k = 4 - 1 = 3
• Valid third sides are at positions from j+1=3 to k=3, which is just position 3 (value 4)
• Count: k - j = 3 - 2 = 1
• This forms triangle (2, 3, 4)

Iteration 3: i=0, j=3 (sides: 2, 4)

• We have nums[0] = 2 and nums[3] = 4
• Sum = 2 + 4 = 6
• No elements after position 3, so k - j = 0
• Count: 0

Iteration 4: i=1, j=2 (sides: 2, 3)

• We have nums[1] = 2 and nums[2] = 3
• Sum = 2 + 3 = 5
• bisect_left([2, 2, 3, 4], 5, lo=3) returns index 4
• k = 4 - 1 = 3
• Count: k - j = 3 - 2 = 1
• This forms triangle (2, 3, 4) with different indices

Iteration 5: i=1, j=3 (sides: 2, 4)

• Sum = 6, no elements after position 3
• Count: 0

Iteration 6: i=2, j=3 (sides: 3, 4)

• Sum = 7, no elements after position 3
• Count: 0

Step 3: Return total count Total = 1 + 1 + 0 + 1 + 0 + 0 = 3

The three valid triangles are:

1. (2, 2, 3) using indices (0, 1, 2)
2. (2, 3, 4) using indices (0, 2, 3)
3. (2, 3, 4) using indices (1, 2, 3)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n² log n)

The algorithm uses a nested loop structure with binary search:

• The outer loop runs n - 2 times where n is the length of the array
• The inner loop runs up to n - 1 - (i + 1) times for each iteration of the outer loop
• For each pair (i, j), a binary search is performed using bisect_left, which takes O(log n) time
• The initial sorting takes O(n log n) time

Overall: O(n log n) for sorting + O(n²) iterations × O(log n) for binary search = O(n² log n)

Space Complexity: O(1) or O(log n)

• The algorithm sorts the input array in-place and uses only a constant amount of extra variables (ans, n, i, j, k)
• If we consider the space used by the sorting algorithm (typically O(log n) for the recursion stack in algorithms like quicksort), then the space complexity is O(log n)
• Otherwise, if we only count the auxiliary space explicitly used by our algorithm, it's O(1)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Handling Zero or Negative Values Incorrectly

A critical pitfall is not considering that the input array might contain zeros or negative values. While negative side lengths don't make physical sense for triangles, the problem doesn't explicitly exclude them. The current solution might count invalid triangles when zeros are present.

Why it's a problem: When the array contains zeros, combinations like [0, 3, 4] would be counted as valid since 0 + 3 = 3 < 4 satisfies our check, but a triangle with a side of length 0 cannot exist.

Solution:

def triangleNumber(self, nums: List[int]) -> int:
    # Filter out non-positive values first
    nums = [x for x in nums if x > 0]
    nums.sort()
    # ... rest of the implementation remains the same

2. Off-by-One Error in Binary Search Result

A common mistake is misunderstanding what bisect_left returns and how to use it. Developers might forget to subtract 1 from the result or might use bisect_right instead, leading to incorrect counts.

Why it's a problem: bisect_left(nums, target, lo=j+1) returns the leftmost position where we could insert target. If we want the last valid index where nums[k] < target, we need to subtract 1. Using this value directly would include triangles where the sum equals the third side (invalid).

Solution:

# Correct approach - subtract 1 to get last valid index
insertion_point = bisect_left(nums, sum_of_two_sides, lo=second_side_idx + 1)
largest_valid_idx = insertion_point - 1

# Alternative using bisect_right (also correct)
largest_valid_idx = bisect_right(nums, sum_of_two_sides - 1, lo=second_side_idx + 1) - 1

3. Not Handling Edge Cases with Array Length

The algorithm assumes there are at least 3 elements in the array. If the array has fewer than 3 elements, the loops still execute but won't cause errors due to the range limits. However, it's cleaner to handle this explicitly.

Why it's a problem: While not causing runtime errors, it's inefficient to process arrays that cannot possibly form any triangles.

Solution:

def triangleNumber(self, nums: List[int]) -> int:
    if len(nums) < 3:
        return 0
  
    nums.sort()
    # ... rest of the implementation

4. Incorrect Count Calculation

A subtle mistake is calculating the count as largest_valid_idx - second_side_idx - 1 or largest_valid_idx - second_side_idx + 1 instead of the correct largest_valid_idx - second_side_idx.

Why it's a problem: The valid third sides are at indices [second_side_idx + 1, ..., largest_valid_idx]. The count is largest_valid_idx - second_side_idx, not off by one in either direction.

Solution:

# Correct: includes all indices from second_side_idx + 1 to largest_valid_idx
triangle_count += largest_valid_idx - second_side_idx

# Wrong: would miss one valid triangle
# triangle_count += largest_valid_idx - second_side_idx - 1

# Wrong: would count one extra invalid triangle  
# triangle_count += largest_valid_idx - second_side_idx + 1