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
20
21
22
23

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    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
18
19
20
21
22

package main

import "sort"

type Solution struct{}

func (s *Solution) 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
17
18

class Solution {
    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
18
19

class Solution {
    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
14
15
16

from typing import List

class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        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
18
19
20
21

pub struct Solution;

impl Solution {
    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
17
18

class Solution {
    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.