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.

Examples

Example 1

1
2
3
4
5
6

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

1
2

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

Constraints

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

Solution

Method 1 – Sort and Two Pointers

Intuition

If we sort the array, for every pair (i, j), we can find the largest k such that nums[i] + nums[j] > nums[k]. This allows us to count valid triangles efficiently.

Approach

  1. Sort the array.
  2. For each index k from 2 to n-1, use two pointers (i=0, j=k-1) to find all pairs (i, j) such that nums[i] + nums[j] > nums[k].
  3. For each valid pair, add (j - i) to the answer and move pointers accordingly.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

#include <vector>
#include <algorithm>
using namespace std;
int triangleNumber(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    int n = nums.size(), count = 0;
    for (int k = n - 1; k >= 2; --k) {
        int i = 0, j = k - 1;
        while (i < j) {
            if (nums[i] + nums[j] > nums[k]) {
                count += (j - i);
                --j;
            } else {
                ++i;
            }
        }
    }
    return count;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import "sort"
func triangleNumber(nums []int) int {
    sort.Ints(nums)
    n, count := len(nums), 0
    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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

public int triangleNumber(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length, count = 0;
    for (int k = n - 1; k >= 2; k--) {
        int i = 0, j = k - 1;
        while (i < j) {
            if (nums[i] + nums[j] > nums[k]) {
                count += (j - i);
                j--;
            } else {
                i++;
            }
        }
    }
    return count;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

fun triangleNumber(nums: IntArray): Int {
    nums.sort()
    var count = 0
    for (k in nums.size - 1 downTo 2) {
        var i = 0
        var j = k - 1
        while (i < j) {
            if (nums[i] + nums[j] > nums[k]) {
                count += (j - i)
                j--
            } else {
                i++
            }
        }
    }
    return count
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def triangleNumber(nums):
    nums.sort()
    n = len(nums)
    count = 0
    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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

pub fn triangle_number(mut nums: Vec<i32>) -> i32 {
    nums.sort();
    let n = nums.len();
    let mut count = 0;
    for k in (2..n).rev() {
        let (mut i, mut j) = (0, k - 1);
        while i < j {
            if nums[i] + nums[j] > nums[k] {
                count += (j - i) as i32;
                j -= 1;
            } else {
                i += 1;
            }
        }
    }
    count
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

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

Complexity

  • ⏰ Time complexity: O(n^2) — Sorting is O(n log n), and the two-pointer scan is O(n^2).
  • 🧺 Space complexity: O(1) — Sorting in-place, only a few variables used.