#611

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Valid Triangle Number

Count all triplets in an integer array that satisfy the triangle inequality to form valid triangles efficiently using sorting and binary search.

array two pointers binary search greedy sorting

Problem Statement

Given an integer array nums, return the number of triplets that can form a triangle when considered as side lengths. A triplet (i,j,k) is valid if nums[i] + nums[j] > nums[k] for sorted indices i<j<k.

Example: nums = [2,2,3,4]. Valid triangles are (2,2,3), (2,3,4), (2,3,4). The output is 3. Another example: nums = [4,2,3,4], output 4.

Examples

Example 1

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

Output: 3

Valid combinations are: 2,3,4 (using the first 2) 2,3,4 (using the second 2) 2,2,3

Example 2

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

Output: 4

Example details omitted.

Constraints

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

Solution Approach

Sort the Array

Sort nums ascendingly so that triangle conditions can be checked efficiently using indices. Sorting guarantees that nums[i] <= nums[j] <= nums[k], simplifying inequality checks.

Use Two Pointers

Iterate over the array using two pointers for the smaller sides and find the maximum third side k such that nums[i]+nums[j]>nums[k]. Move pointers intelligently to count all valid k without redundant checks.

Binary Search Optimization

For each pair (i,j), perform a binary search to locate the largest index k satisfying the triangle inequality. Add k-j to the count, leveraging the sorted order to reduce time complexity from O(n^3) to O(n^2 log n).

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting takes O(n log n). Two-pointer scanning or binary search for each pair yields O(n^2) or O(n^2 log n) total time. Space is O(1) extra if sorting in place, otherwise O(n).

What Interviewers Usually Probe

Sorting the array before counting triplets
Using two pointers or binary search for the third side
Avoiding O(n^3) brute-force enumeration

Common Pitfalls or Variants

Common pitfalls

Not sorting the array first, causing incorrect triangle checks
Ignoring duplicate numbers leading to miscounted triplets
Miscalculating the range of the third side or using incorrect indices

Follow-up variants

Count triangles with perimeter below a given threshold
Find all unique triplets instead of counting them
Allow negative numbers and determine valid triangle counts accordingly

FAQ

What is the best approach for Valid Triangle Number?

Sort the array and use either two pointers or binary search to count all triplets satisfying the triangle inequality.

Can zeros or duplicates affect the triangle count?

Yes, zeros cannot form triangles and duplicates must be considered carefully to avoid double counting valid triplets.

What is the time complexity of the optimal solution?

Sorting takes O(n log n) and counting with two pointers or binary search gives O(n^2) or O(n^2 log n).

Why is binary search useful in this problem?

It finds the largest valid third side efficiently, reducing the need for nested loops and avoiding O(n^3) brute-force checks.

How does GhostInterview handle the triangle inequality pattern?

It guides through sorting, pointer selection, and index calculation to ensure all valid triplets are counted correctly with minimal mistakes.

terminal

Solution

Solution 1: Sorting + Binary Search

A valid triangle must satisfy: **the sum of any two sides is greater than the third side**. That is:

1

2

3

4

5

6

7

8

9

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        ans, n = 0, len(nums)
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                k = bisect_left(nums, nums[i] + nums[j], lo=j + 1) - 1
                ans += k - j
        return ans

Continue Practicing

#826 most profit assigning work #581 shortest unsorted continuous subarray #658 find k closest elements