Two Pointer Algorithm to Count Triangle Triplets in an Array

Given a list of non-negative integers nums, return the total number of 3 unique numbers that can create a triangle.

Constraints
n ≤ 1,000 where n is the length of nums
Example 1
Input
nums = [7, 8, 8, 9, 100]
Output
4
Explanation
We can make these triangles:
7, 8, 8
7, 8, 9
7, 8, 9 (using the other 8)
8, 8, 9

Finding Triangle Triplets using Two Pointer

We can sort the array, and bruteforce the longest edge, and perform a two pointer algorithm on the remainder two numbers. If the sum of the less two is bigger than the longest, then we need to accumulate the answer by the difference of the two pointers, and move one pointer towards the smaller one.

If the sum of two is smaller than the longest, the current three numbers won’t make up a valid triangle triplets, then we have to move the lower point – checking if next pair is possible or not.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution:
    def triangleTriplets(self, nums):
        count = 0
        nums.sort()
        n = len(nums)
        for i in range(n - 1, 1, -1):
            l, r = 0, i - 1
            while l < r:
                if nums[l] + nums[r] <= nums[i]:
                    l += 1
                else:
                    count += r - l
                    r -= 1
        return count

class Solution:
    def triangleTriplets(self, nums):
        count = 0
        nums.sort()
        n = len(nums)
        for i in range(n - 1, 1, -1):
            l, r = 0, i - 1
            while l < r:
                if nums[l] + nums[r] <= nums[i]:
                    l += 1
                else:
                    count += r - l
                    r -= 1
        return count

We can sort in reverse order as well.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution:
    def triangleTriplets(self, nums):
        nums.sort(reverse=True)
        ans = 0
        n = len(nums)
        for i in range(n):
            j = i + 1
            k = n - 1
            while j < k:
                if nums[i] >= nums[j] + nums[k]:                    
                    k -= 1
                else:
                    ans += k - j
                    j += 1
        return ans

class Solution:
    def triangleTriplets(self, nums):
        nums.sort(reverse=True)
        ans = 0
        n = len(nums)
        for i in range(n):
            j = i + 1
            k = n - 1
            while j < k:
                if nums[i] >= nums[j] + nums[k]:                    
                    k -= 1
                else:
                    ans += k - j
                    j += 1
        return ans

–EOF (The Ultimate Computing & Technology Blog) —