POTD #19 - Count the number of possible triangles | Geeks For Geeks

{% raw %}

Problem Statement

Geeks For Geeks – https://www.geeksforgeeks.org/problems/count-possible-triangles-1587115620/1

Given an integer array arr[]. Find the number of triangles that can be formed with three different array elements as lengths of three sides of the triangle.  A triangle with three given sides is only possible if sum of any two sides is always greater than the third side.

Input: arr[] = [4, 6, 3, 7]Output: 3Explanation: There are three triangles possible [3, 4, 6], [4, 6, 7] and [3, 6, 7]. Note that [3, 4, 7] is not a possible triangle.  

Input: arr[] = [10, 21, 22, 100, 101, 200, 300]Output: 6Explanation: There can be 6 possible triangles: [10, 21, 22], [21, 100, 101], [22, 100, 101], [10, 100, 101], [100, 101, 200] and [101, 200, 300]

My Approach

class Solution:    #Function to count the number of possible triangles.    def countTriangles(self, arr):        # code here        arr.sort()        n = len(arr)        cnt = 0        for itr in range(2, n):            left = 0            right = itr - 1                        while left < right:                                if arr[left] + arr[right] > arr[itr]:                    cnt += right - left                    right -= 1                else:                    left += 1        return cnt

{% endraw %}