611. Valid Triangle Number - Solution

The 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.

Example 1:

Input: nums = [2,2,3,4]
Output: 3
Explanation: 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

Constraints:

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

Approach overview

Problem Overview: You are given an integer array where each value represents a potential side length. The task is to count how many triplets (i, j, k) can form a valid triangle. A triangle is valid only if the triangle inequality holds: the sum of any two sides must be greater than the third side.

Approach 1: Brute Force (O(n^3) time, O(1) space)

The straightforward way is to check every possible triplet. Iterate three nested loops and pick indices i, j, and k. For each combination, verify the triangle inequality conditions: a + b > c, a + c > b, and b + c > a. If all conditions hold, increment the count. This approach works but becomes slow for large inputs because it evaluates every triplet explicitly. It’s useful for understanding the constraint logic but rarely acceptable in interviews due to the cubic runtime.

Approach 2: Sorting + Two-Pointer Technique (O(n^2) time, O(1) space)

The key optimization comes from sorting the array first. Once sorted, you only need to check one inequality: nums[left] + nums[right] > nums[k]. Fix the largest side at index k, then use two pointers (left and right) scanning the prefix of the array. If the sum of the two smaller sides is greater than nums[k], then every element between left and right with right forms a valid triangle, so you add right - left to the count and move right leftward. Otherwise move left forward. Sorting combined with the two pointers pattern reduces the search dramatically and runs in quadratic time.

Approach 3: Sorting + Binary Search (O(n^2 log n) time, O(1) space)

Another optimization after sorting is to fix two sides i and j, then use binary search to find the largest index k such that nums[i] + nums[j] > nums[k]. All indices between j+1 and k form valid triangles with the chosen pair. This reduces the third loop to a logarithmic lookup. The method is slightly slower than the two-pointer approach but still far better than brute force.

Both optimized solutions rely on sorting, a common pattern when solving array problems involving order-based constraints. Sorting allows you to reason about the triangle inequality with fewer checks.

Recommended for interviews: The sorting + two-pointer solution is what most interviewers expect. It shows that you recognize the triangle inequality optimization and can apply the two-pointer pattern effectively. Explaining the brute force approach first demonstrates problem understanding, then improving it to the O(n^2) solution shows strong algorithmic thinking.

Approach 1: Two-Pointer Technique

First, sort the array. Then, iterate through the array by selecting the third side of the triplet. Use a two-pointer technique to find valid pairs for the first and second sides. For each third side, initialize two pointers, one starting at the beginning of the list and the other just before the third side. Check the sum of the elements at the two pointers and compare it to the third side. If they form a valid triangle, move the inner pointer inward; otherwise, adjust the pointers accordingly.

Python

class Solution:
    def triangleNumber(self, nums):
        nums.sort()
        count = 0
        for i in range(len(nums) - 1, 1, -1):
            left, right = 0, i - 1
            while left < right:
                if nums[left] + nums[right] > nums[i]:
                    count += right - left
                    right -= 1
                else:
                    left += 1
        return count

# Example usage:
sol = Solution()
print(sol.triangleNumber([2, 2, 3, 4]))

Java

import java.util.*;

public class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        for (int i = nums.length - 1; i >= 2; i--) {
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    count += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return count;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {2, 2, 3, 4};
        System.out.println(sol.triangleNumber(nums));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int count = 0;
        for (int i = nums.size() - 1; i >= 2; --i) {
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    count += right - left;
                    --right;
                } else {
                    ++left;
                }
            }
        }
        return count;
    }
};

int main() {
    vector<int> nums = {2, 2, 3, 4};
    Solution sol;
    cout << sol.triangleNumber(nums) << endl;
    return 0;
}

JavaScript

function triangleNumber(nums) {
    nums.sort((a, b) => a - b);
    let count = 0;
    for (let i = nums.length - 1; i >= 2; i--) {
        let left = 0, right = i - 1;
        while (left < right) {
            if (nums[left] + nums[right] > nums[i]) {
                count += right - left;
                right--;
            } else {
                left++;
            }
        }
    }
    return count;
}

console.log(triangleNumber([2, 2, 3, 4]));

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

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

int triangleNumber(int* nums, int numsSize) {
    if (numsSize < 3) return 0;
    qsort(nums, numsSize, sizeof(int), compare);
    int count = 0;
    for (int i = numsSize - 1; i >= 2; i--) {
        int left = 0, right = i - 1;
        while (left < right) {
            if (nums[left] + nums[right] > nums[i]) {
                count += right - left;
                right--;
            } else {
                left++;
            }
        }
    }
    return count;
}

int main() {
    int nums[] = {2, 2, 3, 4};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("%d\n", triangleNumber(nums, size));
    return 0;
}

using System;

public class Solution {
    public int TriangleNumber(int[] nums) {
        Array.Sort(nums);
        int count = 0;
        for (int i = nums.Length - 1; i >= 2; i--) {
            int left = 0, right = i - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[i]) {
                    count += right - left;
                    right--;
                } else {
                    left++;
                }
            }
        }
        return count;
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        Console.WriteLine(sol.TriangleNumber(new int[] {2, 2, 3, 4}));
    }
}

This Python solution sorts the list and uses two pointers, similar to other languages, to efficiently count the number of triplets satisfying triangle conditions.

Complexity

Time Complexity: O(n^2) due to sorting the list and evaluating possible triplets.
Space Complexity: O(1), used to store variable count and pointers.

Try this approach in the editor

Approach 2: Brute Force Approach

This approach involves checking every possible triplet from the array to see if they can form a triangle by comparing their sums directly. This solution is straightforward but less efficient since it considers all combinations without optimizations such as sorting or double pointers.

Python

class Solution:
    def triangleNumber(self, nums):
        count = 0
        n = len(nums)
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                for k in range(j + 1, n):
                    if nums[i] + nums[j] > nums[k] and nums[i] + nums[k] > nums[j] and nums[j] + nums[k] > nums[i]:
                        count += 1
        return count

# Example usage:
sol = Solution()
print(sol.triangleNumber([2, 2, 3, 4]))

Java

public class Solution {
    public int triangleNumber(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (nums[i] + nums[j] > nums[k] && nums[i] + nums[k] > nums[j] && nums[j] + nums[k] > nums[i]) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums = {2, 2, 3, 4};
        System.out.println(sol.triangleNumber(nums));
    }
}

C++

#include <iostream>
#include <vector>

using namespace std;

bool isValidTriangle(int a, int b, int c) {
    return a + b > c && a + c > b && b + c > a;
}

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int count = 0;
        int n = nums.size();
        for (int i = 0; i < n - 2; ++i) {
            for (int j = i + 1; j < n - 1; ++j) {
                for (int k = j + 1; k < n; ++k) {
                    if (isValidTriangle(nums[i], nums[j], nums[k])) count++;
                }
            }
        }
        return count;
    }
};

int main() {
    vector<int> nums = {2, 2, 3, 4};
    Solution sol;
    cout << sol.triangleNumber(nums) << endl;
    return 0;
}

JavaScript

function triangleNumber(nums) {
    let count = 0;
    for (let i = 0; i < nums.length - 2; i++) {
        for (let j = i + 1; j < nums.length - 1; j++) {
            for (let k = j + 1; k < nums.length; k++) {
                if (nums[i] + nums[j] > nums[k] && nums[i] + nums[k] > nums[j] && nums[j] + nums[k] > nums[i]) {
                    count++;
                }
            }
        }
    }
    return count;
}

console.log(triangleNumber([2, 2, 3, 4]));

#include <stdio.h>
#include <stdbool.h>

bool isValidTriangle(int a, int b, int c) {
    return a + b > c && a + c > b && b + c > a;
}

int triangleNumber(int* nums, int numsSize) {
    int count = 0;
    for (int i = 0; i < numsSize - 2; i++) {
        for (int j = i + 1; j < numsSize - 1; j++) {
            for (int k = j + 1; k < numsSize; k++) {
                if (isValidTriangle(nums[i], nums[j], nums[k])) count++;
            }
        }
    }
    return count;
}

int main() {
    int nums[] = {2, 2, 3, 4};
    int size = sizeof(nums) / sizeof(nums[0]);
    printf("%d\n", triangleNumber(nums, size));
    return 0;
}

using System;

public class Solution {
    public int TriangleNumber(int[] nums) {
        int count = 0;
        for (int i = 0; i < nums.Length - 2; i++) {
            for (int j = i + 1; j < nums.Length - 1; j++) {
                for (int k = j + 1; k < nums.Length; k++) {
                    if (nums[i] + nums[j] > nums[k] && nums[i] + nums[k] > nums[j] && nums[j] + nums[k] > nums[i]) {
                        count++;
                    }
                }
            }
        }
        return count;
    }

    public static void Main(string[] args) {
        Solution sol = new Solution();
        Console.WriteLine(sol.TriangleNumber(new int[] {2, 2, 3, 4}));
    }
}

The Python implementation relies on three nested loops to test all combinations, ensuring each qualifies the triangle inequality condition for valid triplets.

Complexity

Time Complexity: O(n^3), assessing all possible groupings of triplets.
Space Complexity: O(1), consuming just the needed storage for counters and loop control.

Try this approach in the editor

Approach 3: Sorting + Binary Search

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

$a + b \gt c \tag{1}

a + c \gt b \tag{2}

b + c \gt a \tag{3}

If we arrange the sides in ascending order, i.e., a leq b leq c, then obviously conditions (2) and (3) are satisfied. We only need to ensure that condition (1) is also satisfied to form a valid triangle.

We enumerate i in the range [0, n - 3], enumerate j in the range [i + 1, n - 2], and perform binary search in the range [j + 1, n - 1] to find the first index left that is greater than or equal to nums[i] + nums[j]. Then, the values of k in the range [j + 1, left - 1] satisfy the condition, and we add them to the result ans.

The time complexity is O(n^2log n), and the space complexity is O(log n), where n$ is the length of the array.

TypeScript

function triangleNumber(nums: number[]): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            const sum = nums[i] + nums[j];
            let k = _.sortedIndex(nums, sum, j + 1) - 1;
            if (k > j) {
                ans += k - j;
            }
        }
    }
    return ans;
}

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

Rust

impl Solution {
    pub fn triangle_number(mut nums: Vec<i32>) -> i32 {
        nums.sort();
        let n = nums.len();
        let mut ans = 0;
        for i in 0..n.saturating_sub(2) {
            for j in i + 1..n.saturating_sub(1) {
                let sum = nums[i] + nums[j];
                let mut left = j + 1;
                let mut right = n;
                while left < right {
                    let mid = (left + right) / 2;
                    if nums[mid] < sum {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                if left > j + 1 {
                    ans += (left - 1 - j) as i32;
                }
            }
        }
        ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Two-Pointer Technique	Time Complexity: O(n^2) due to sorting the list and evaluating possible triplets. Space Complexity: O(1), used to store variable count and pointers.
Brute Force Approach	Time Complexity: O(n^3), assessing all possible groupings of triplets. Space Complexity: O(1), consuming just the needed storage for counters and loop control.
Sorting + Binary Search	–

Complexity analysis

Approach	Time	Space	When to Use
Brute Force (Triple Loop)	O(n^3)	O(1)	Good for understanding triangle inequality or validating small inputs
Sorting + Binary Search	O(n^2 log n)	O(1)	When you want a clear improvement over brute force with predictable searches
Sorting + Two Pointers	O(n^2)	O(1)	Best approach for interviews and large arrays

Frequently asked questions

Is Valid Triangle Number easy or hard?

Valid Triangle Number is generally considered a medium difficulty problem. The triangle inequality is simple, but recognizing that sorting enables a two-pointer counting strategy is the key insight.

Valid Triangle Number Python/Java solution

Most implementations follow the same pattern: sort the array, iterate the largest side index from the end, and run a two-pointer search for valid pairs. The logic translates directly to Python, Java, C++, C#, and JavaScript with identical O(n^2) complexity.

How to solve Valid Triangle Number in O(n^2)?

First sort the array so the largest side is easy to fix. For each index k as the largest side, place two pointers at the start and just before k. If nums[left] + nums[right] > nums[k], then all elements between left and right form valid triangles with right, so add right - left and move the right pointer.

What is the best approach for Valid Triangle Number?

The best approach is sorting the array followed by a two-pointer scan. After sorting, fix the largest side and use two pointers to find pairs whose sum is greater than that side. This counts multiple valid triangles at once and runs in O(n^2) time with O(1) extra space.

Is Valid Triangle Number asked at Google/Amazon/Meta?

Triangle inequality and two-pointer counting problems frequently appear in interviews at companies like Amazon, Meta, and Google. Variations of this problem test understanding of sorting, pointer movement, and counting combinations efficiently.

What data structure is used in Valid Triangle Number?

The core data structure is a simple array. The algorithm relies on sorting the array and then applying the two-pointer technique to scan combinations efficiently without extra memory.

What is the time complexity of Valid Triangle Number?

The optimal solution runs in O(n^2) time after sorting the array. Sorting takes O(n log n), and the two-pointer scan processes each element pair at most once. The brute force approach is O(n^3) because it checks every triplet.

Valid Triangle Number solution and explanation

The problem

Approach overview

Approach 1: Two-Pointer Technique

Approach 2: Brute Force Approach

Approach 3: Sorting + Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Valid Triangle Number solution and explanation

The problem

Approach overview

Approach 1: Two-Pointer Technique

Approach 2: Brute Force Approach

Approach 3: Sorting + Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems