Given an unsorted array arr[] of n positive integers. Find the number of triangles that can be formed with three different array elements as lengths of three sides of triangles. 
Example 1:
Input: 
n = 3
arr[] = {3, 5, 4}
Output: 
1
Explanation: 
A triangle is possible 
with all the elements 5, 3 and 4.
Example 2:
Input: 
n = 5
arr[] = {6, 4, 9, 7, 8}
Output: 
10
Explanation: 
There are 10 triangles
possible  with the given elements like
(6,4,9), (6,7,8),...
 
Your Task: 
This is a function problem. You only need to complete the function findNumberOfTriangles() that takes arr[] and n as input parameters and returns the count of total possible triangles.
Expected Time Complexity: O(n^{2}).
Expected Space Complexity: O(1).
Constraints:
3 <= n <= 10^{3}
1 <= arr[i] <= 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Starter code: #User function Template for python3

class Solution:
    #Function to count the number of possible triangles.
    def findNumberOfTriangles(self, arr, n):
        #code here

Solutions:
class Solution:

	def findNumberOfTriangles(self, arr, n):
		arr.sort()
		ans = 0
		for i in range(n - 1, 0, -1):
			left = 0
			right = i - 1
			while left < right:
				if arr[left] + arr[right] > arr[i]:
					ans += right - left
					right -= 1
				else:
					left += 1
		return ans


class Solution:

	def findNumberOfTriangles(self, arr, n):
		arr.sort()
		count = 0
		for i in range(n - 1, 0, -1):
			(l, r) = (0, i - 1)
			while l < r:
				if arr[l] + arr[r] > arr[i]:
					count = count + (r - l)
					r = r - 1
				else:
					l = l + 1
		return count


from itertools import *

class Solution:

	def findNumberOfTriangles(self, arr, n):
		arr.sort()
		count = 0
		for c in range(n - 1, 1, -1):
			b = c - 1
			a = 0
			while b > a:
				if arr[a] + arr[b] > arr[c]:
					count += b - a
					b -= 1
				else:
					a += 1
		return count


class Solution:

	def findNumberOfTriangles(self, arr, n):
		arr.sort()
		count = 0
		for i in range(n - 2):
			k = i + 2
			for j in range(i + 1, n):
				while n > k and arr[i] + arr[j] > arr[k]:
					k += 1
				if k > j:
					count += k - j - 1
		return count


class Solution:

	def findNumberOfTriangles(self, arr, n):
		arr.sort()
		i = len(arr) - 1
		answer = 0
		while i >= 0:
			l = 0
			r = i - 1
			while l < r:
				if arr[l] + arr[r] > arr[i]:
					answer = answer + r - l
					r -= 1
				else:
					l += 1
			i -= 1
		return answer


class Solution:

	def findNumberOfTriangles(self, arr, n):
		ct = 0
		arr.sort()
		for i in range(n):
			(j, k) = (0, i - 1)
			while j < k:
				if arr[j] + arr[k] > arr[i]:
					ct += k - j
					k -= 1
				else:
					j += 1
		return ct


class Solution:

	def findNumberOfTriangles(self, arr, n):
		if n < 3:
			return 0
		a = sorted(arr)
		count = 0
		for i in range(n - 1, 0, -1):
			l = 0
			r = i - 1
			while l < r:
				if a[l] + a[r] > a[i]:
					count += r - l
					r -= 1
				else:
					l += 1
		return count


class Solution:

	def findNumberOfTriangles(self, arr, n):
		arr = sorted(arr)
		count = 0
		for i in range(n - 1, 1, -1):
			j = i - 1
			k = 0
			while j > k:
				if arr[k] + arr[j] > arr[i]:
					count += j - k
					j -= 1
				else:
					k += 1
		return count


class Solution:

	def findNumberOfTriangles(self, arr, n):
		arr.sort()
		count = 0
		if len(arr) < 3:
			return 0
		for i in range(n - 1, 1, -1):
			j = i - 1
			k = 0
			while k < j:
				if arr[k] + arr[j] > arr[i]:
					count = count + j - k
					j = j - 1
				else:
					k = k + 1
		return count


class Solution:

	def findNumberOfTriangles(self, arr, n):
		n = len(arr)
		arr.sort()
		count = 0
		for i in range(n - 1, 0, -1):
			low = 0
			high = i - 1
			while low < high:
				if arr[low] + arr[high] > arr[i]:
					count += high - low
					high -= 1
				else:
					low += 1
		return count


class Solution:

	def findNumberOfTriangles(self, arr, n):
		arr = sorted(arr, reverse=True)
		count = 0
		for i in range(n - 2):
			(l, r) = (i + 1, n - 1)
			while l < r:
				if arr[l] + arr[r] <= arr[i]:
					r -= 1
				else:
					count += r - l
					l += 1
		return count


class Solution:

	def findNumberOfTriangles(self, arr, n):

		def find2Numbers(a, y):
			k = 0
			l = len(a) - 1
			c = 0
			while k < l:
				if y < a[k] + a[l]:
					c += l - k
					k += 1
				elif y >= a[k] + a[l]:
					l -= 1
			return c
		arr.sort(reverse=True)
		total = 0
		for i in range(len(arr)):
			x = arr[i]
			total += find2Numbers(arr[i + 1:len(arr)], x)
		return total


class Solution:

	def findNumberOfTriangles(self, a, n):
		a.sort()
		c = 0
		for i in range(n - 1, 1, -1):
			b = i - 1
			q = 0
			while b > q:
				if a[q] + a[b] > a[i]:
					c += b - q
					b -= 1
				else:
					q += 1
		return c


class Solution:

	def findNumberOfTriangles(self, arr, n):
		arr.sort()
		ans = 0
		i = 2
		while i < len(arr):
			left = 0
			right = i - 1
			while left < right:
				if arr[left] + arr[right] > arr[i]:
					ans += right - left
					right -= 1
				else:
					left += 1
			i += 1
		return ans


class Solution:

	def findNumberOfTriangles(self, arr, n):
		cnt = 0
		arr.sort()
		for c in range(len(arr) - 1, -3, -1):
			a = 0
			b = c - 1
			while a < b:
				if arr[a] + arr[b] > arr[c]:
					cnt += b - a
					b -= 1
				else:
					a += 1
		return cnt


class Solution:

	def findNumberOfTriangles(self, a, n):
		ans = 0
		a.sort()
		for i in range(n - 2, 0, -1):
			j = i + 1
			k = 0
			while k < i:
				if j == n:
					ans += j - i - 1
					k += 1
				elif a[k] + a[i] > a[j]:
					j += 1
				else:
					ans += j - i - 1
					k += 1
		return ans


class Solution:

	def findNumberOfTriangles(self, arr, n):
		arr.sort()
		count = 0
		for max in range(n - 1, 1, -1):
			a = 0
			b = max - 1
			while b > a:
				if arr[a] + arr[b] > arr[max]:
					count += b - a
					b -= 1
				else:
					a += 1
		return count


class Solution:

	def findNumberOfTriangles(self, arr, n):
		arr.sort()
		res = 0
		for i in range(n - 1, -1, -1):
			z = arr[i]
			(s, e) = (0, i - 1)
			while e > s:
				if arr[e] + arr[s] > z:
					res += e - s
					e -= 1
				else:
					s += 1
		return res


class Solution:

	def nC2(self, n):
		return n * (n - 1) / 2

	def findNumberOfTriangles(self, arr, n):
		arr.sort()
		j = n - 1
		count = 0
		while j >= 2:
			i = 0
			k = j - 1
			c = arr[j]
			while i < k:
				a = arr[i]
				b = arr[k]
				if a + b > c:
					count = count + (k - i)
					k = k - 1
				else:
					i = i + 1
			j = j - 1
		return count


class Solution:

	def findNumberOfTriangles(self, arr, n):
		arr.sort()
		res = 0
		for c in range(n - 1, 1, -1):
			a = 0
			b = c - 1
			while a < b:
				if arr[a] + arr[b] > arr[c]:
					res += b - a
					b -= 1
				else:
					a += 1
		return res


class Solution:

	def findNumberOfTriangles(self, arr, n):
		arr.sort()
		ans = 0
		for idx in range(n - 1, -1, -1):
			l = 0
			r = idx - 1
			while l < r:
				if arr[l] + arr[r] > arr[idx]:
					ans += r - l
					r -= 1
				else:
					l += 1
		return ans


class Solution:

	def findNumberOfTriangles(self, arr, n):
		arr.sort()
		total = 0
		for i in range(n - 1, 1, -1):
			high = i - 1
			low = 0
			while low < high:
				side_sum = arr[low] + arr[high]
				if side_sum > arr[i]:
					total += high - low
					high -= 1
				else:
					low += 1
		return total


class Solution:

	def findNumberOfTriangles(self, arr, n):
		ans = 0
		arr.sort()
		for i in range(0, n - 2):
			third = i + 2
			for j in range(i + 1, n):
				while third < n and arr[i] + arr[j] > arr[third]:
					third += 1
				ans += third - j - 1
		return ans


class Solution:

	def findNumberOfTriangles(self, arr, n):
		arr.sort()
		count = 0
		for i in range(n - 2):
			(j, p) = (i + 1, i + 2)
			while j < n - 1:
				if arr[i] + arr[j] <= arr[p]:
					count += p - j - 1
					j += 1
				else:
					p += 1
				if p >= n:
					count += sum([p - k - 1 for k in range(j, n - 1)])
					break
		return count


class Solution:

	def findNumberOfTriangles(self, arr, n):
		c = 0
		arr.sort()
		for i in range(n - 1, 0, -1):
			x = 0
			y = i - 1
			while x < y:
				if arr[x] + arr[y] > arr[i]:
					c += y - x
					y -= 1
				else:
					x += 1
		return c