Valid Triangle Number - Practice Coding Problems

Valid Triangle Number - Problem

Given an integer array nums, return the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.

Triangle Validity Rule: For three sides a, b, and c to form a valid triangle, they must satisfy: a + b > c, a + c > b, and b + c > a.

Note: The triangle inequality states that the sum of any two sides must be greater than the third side for all three combinations.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: Valid triangles are: (2,2,3) since 2+2=4>3, 2+3=5>2, 2+3=5>2; (2,3,4) since 2+3=5>4, 2+4=6>3, 3+4=7>2; (2,3,4) with the other 2. Total: 3 triangles.

Example 2 — No Valid Triangles

$ Input: nums = [1,2,3]

› Output: 0

💡 Note: The only triplet is (1,2,3). Check: 1+2=3, which is not greater than 3, so this cannot form a triangle.

Example 3 — All Valid

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

› Output: 4

💡 Note: After sorting [2,3,4,4]: (2,3,4), (2,4,4), (3,4,4), (2,4,4) - all satisfy triangle inequality. Total: 4 triangles.

Constraints

1 ≤ nums.length ≤ 1000
0 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array of potential triangle side lengths

Triangle Check

Apply triangle inequality: sum of any two sides > third side

Count Result

Return total number of valid triangle triplets

Key Takeaway

🎯 Key Insight: After sorting, we only need to check if the sum of two smaller sides exceeds the largest side

Asked in

a Amazon 25 M Microsoft 18 G Google 15 Apple 12

The key insight is that after sorting the array, we only need to check if the sum of two smaller sides is greater than the largest side. The optimal approach uses sorting with two pointers for O(n²) time complexity. Time: O(n²), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Sort + Binary Search	O(n² log n)	O(1)	Sort array and use binary search to find the count of valid triangles for each pair
Brute Force - Check All Triplets	O(n³)	O(1)	Check every possible combination of three numbers to see if they form a valid triangle
Sort + Two Pointers	O(n²)	O(1)	Sort the array first, then use two pointers to efficiently count valid triangles

Sort + Binary Search — Algorithm Steps

Step 1: Sort the array
Step 2: For each pair (i,j) where i < j
Step 3: Use binary search to find largest valid third side
Step 4: Count all valid triangles for this pair

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort & Fix Pair

Sort array and fix two sides as smaller sides

Binary Search

Find largest valid third side using binary search

Count Range

Count all elements in the valid range

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int binarySearch(int* nums, int target, int start, int end) {
    int left = start, right = end;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

int solution(int* nums, int numsSize) {
    qsort(nums, numsSize, sizeof(int), compare);
    int count = 0;
    
    for (int i = 0; i < numsSize; i++) {
        for (int j = i + 1; j < numsSize; j++) {
            // Find the largest k such that nums[i] + nums[j] > nums[k]
            int target = nums[i] + nums[j];
            int k = binarySearch(nums, target, j + 1, numsSize);
            
            // All elements from j+1 to k-1 form valid triangles
            if (k - j - 1 > 0) {
                count += k - j - 1;
            }
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for array input
    int nums[1000];
    int size = 0;
    char* token = strtok(line + 1, ",]");
    while (token != NULL) {
        nums[size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    printf("%d\n", solution(nums, size));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² log n)

O(n log n) sorting plus O(n²) pairs with O(log n) binary search each

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

82.0K Views

Medium Frequency

~25 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort + Binary Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler