Problem Statement in English

You’re 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.

Approach

We first need to know the triangle inequality theorem: the sum of the lengths of any two sides of a triangle must be greater than the length of the third side.

Now, if we pick 2 elements from the array, say nums[i] and nums[j] (where i < j), then to satisfy the triangle inequality theorem, the third element nums[k] must be less than nums[i] + nums[j].

So let’s do this in a structured way. Let’s sort the array. This way, as we pick 2 elements, using 2 pointers, then we can use binary search to find the maximum index k such that nums[k] < nums[i] + nums[j]. The number of valid k for this pair of i and j would be k - j (since k must be greater than j).

It’s probably easier to read the code.

Solution in Python


class Solution:
    def triangleNumber(self, nums: List[int]) -> int:
        nums.sort()
        l = len(nums)
        res = 0

        for i in range(l-2):
            for j in range(i + 1, l-1):
                s = nums[i] + nums[j]
                k = bisect_right(nums, s-1)
                space = k - j - 1 # -1 to exclude j itself
                if space < 0:
                    continue
                else:
                    res += space

        return res

Complexity

  • Time: $O(n^2 \log n)$
    Since we use 2 nested loops and a binary search inside the inner loop.

  • Space: $O(1)$
    Since we use only a constant amount of extra space.

And we are done.