Given an array of size n, a triplet (a[i], a[j], a[k]) is called a Magic Triplet if a[i] < a[j] < a[k] and i < j < k.  Count the number of magic triplets in a given array.
 
Example 1:
Input: arr = [3, 2, 1]
Output: 0
Explanation: There is no magic triplet.
Example 2:
Input: arr = [1, 2, 3, 4]
Output: 4
Explanation: Fours magic triplets are 
(1, 2, 3), (1, 2, 4), (1, 3, 4) and 
(2, 3, 4).
 
Your Task:
You don't need to read or print anything. Your task is to complete the function countTriplets() which takes the array nums[] as input parameter and returns the number of magic triplets in the array.
 
Expected Time Complexity: O(N^{2}) 
Expected Space Complexity: O(1)
 
Constraints:
1 <= length of array <= 1000
1 <= arr[i] <= 100000

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(1)

Starter code:
#User function Template for python3



class Solution:

	def countTriplets(self, nums):

		# Code here

Solutions:
class Solution:

	def countTriplets(self, arr):
		cnt = 0
		n = len(arr)
		li = [{1: 1, 2: 0, 3: 0} for i in range(n)]
		for i in range(1, n):
			for j in range(i):
				if arr[i] > arr[j]:
					li[i][2] += li[j][1]
					li[i][3] += li[j][2]
			cnt = cnt + li[i][3]
		return cnt


class Solution:

	def countTriplets(self, nums):
		if len(nums) < 3:
			return 0
		count = 0
		(left, right) = (0, 0)
		for i in range(1, len(nums) - 1):
			(left, right) = (0, 0)
			for j in range(0, i):
				if nums[j] < nums[i]:
					left += 1
			for j in range(i + 1, len(nums)):
				if nums[j] > nums[i]:
					right += 1
			count += left * right
		return count


class Solution:

	def countTriplets(self, nums):
		n = len(nums)
		res = 0
		for j in range(1, n - 1):
			smaller = 0
			larger = 0
			for i in range(j):
				if nums[i] < nums[j]:
					smaller += 1
			for k in range(j + 1, n):
				if nums[j] < nums[k]:
					larger += 1
			res += smaller * larger
		return res


class Solution:

	def countTriplets(self, nums):
		n = len(nums)
		left = [0] * n
		for i in range(1, n):
			for j in range(i):
				if nums[j] < nums[i]:
					left[i] += 1
		right = [0] * n
		for i in range(n - 1):
			for j in range(i + 1, n):
				if nums[j] > nums[i]:
					right[i] += 1
		c = 0
		for i in range(1, n - 1):
			c += left[i] * right[i]
		return c


from sortedcontainers import SortedList

class Solution:

	def countTriplets(self, nums):
		left = SortedList()
		right = SortedList(nums)
		ans = 0
		for x in nums:
			smaller = left.bisect_left(x)
			larger = len(right) - right.bisect_right(x)
			ans += smaller * larger
			left.add(x)
			right.remove(x)
		return ans


class Solution:

	def countTriplets(self, a):
		ans = 0
		n = len(a)
		for i in range(1, n - 1):
			small = 0
			for j in range(0, i):
				if a[j] < a[i]:
					small += 1
			large = 0
			for j in range(i + 1, n):
				if a[j] > a[i]:
					large += 1
			ans += large * small
		return ans


class Solution:

	def countTriplets(self, nums):
		l = len(nums)
		sum = 0
		for i in range(0, l - 1):
			r = 0
			le = 0
			for j in range(i + 1, l):
				if nums[j] > nums[i]:
					r += 1
			for k in range(0, i):
				if nums[k] < nums[i]:
					le += 1
			sum += le * r
		return sum


class Solution:

	def countTriplets(self, nums):
		res = 0
		n = len(nums)
		for i in range(1, n - 1):
			(l, r) = (0, 0)
			for j in range(0, i):
				if nums[j] < nums[i]:
					l += 1
			for j in range(i + 1, n):
				if nums[j] > nums[i]:
					r += 1
			res += l * r
		return res


class Solution:

	def countTriplets(self, nums):
		n = len(nums)
		ans = 0
		temp = [0] * n
		for i in range(n - 1):
			for j in range(i + 1, n):
				if nums[j] > nums[i]:
					temp[i] += 1
		for i in range(n - 1):
			for j in range(i + 1, n):
				if nums[j] > nums[i]:
					ans += temp[j]
		return ans


class Solution:

	def countTriplets(self, nums):

		def countlessinleft(arr, i):
			c = 0
			for item in arr[:i + 1]:
				if item < arr[i]:
					c += 1
			return c

		def countmaxinright(arr, i):
			c = 0
			for item in arr[i:]:
				if item > arr[i]:
					c += 1
			return c
		ans = 0
		for i in range(len(nums)):
			ans += countlessinleft(nums, i) * countmaxinright(nums, i)
		return ans


class Solution:

	def countTriplets(self, nums):
		count = 0
		n = len(nums)
		for i in range(1, n - 1):
			(cl, cr) = (0, 0)
			for k in range(i):
				if nums[k] < nums[i]:
					cl = cl + 1
			for l in range(i + 1, n):
				if nums[i] < nums[l]:
					cr = cr + 1
			count = count + cl * cr
		return count


class Solution:

	def countTriplets(self, A):
		a = 0
		b = 0
		c = 0
		n = len(A)
		for i in range(1, n):
			for j in range(0, i):
				if A[j] < A[i]:
					a += 1
			for k in range(i + 1, n):
				if A[k] > A[i]:
					b += 1
			c += a * b
			a = 0
			b = 0
		return c


class Solution:

	def countTriplets(self, nums):
		n = len(nums)
		ans = 0
		for i in range(n):
			count_left = 0
			count_right = 0
			for j in range(n):
				if j < i:
					if nums[j] < nums[i]:
						count_left += 1
				elif nums[j] > nums[i]:
					count_right += 1
			ans += count_left * count_right
		return ans


class Solution:

	def countTriplets(self, nums):
		N = len(nums)
		arr = [0 for i in range(N)]
		brr = [0 for i in range(N)]
		for i in range(1, N):
			for j in range(0, i):
				if nums[i] > nums[j]:
					arr[i] += 1
		for i in range(1, N):
			for j in range(i + 1, N):
				if nums[i] < nums[j]:
					brr[i] += 1
		ans = 0
		for i in range(N):
			ans += arr[i] * brr[i]
		return ans


class Solution:

	def countTriplets(self, nums):
		n = len(nums)
		ans = 0
		for i in range(1, n - 1):
			smaller = 0
			for j in range(i - 1, -1, -1):
				if nums[i] > nums[j]:
					smaller += 1
			greater = 0
			for k in range(i + 1, n):
				if nums[k] > nums[i]:
					greater += 1
			ans += smaller * greater
		return ans


class Solution:

	def countTriplets(self, arr):
		n = len(arr)
		l = [0] * n
		for i in range(n - 1):
			for j in range(i + 1, n):
				if arr[j] > arr[i]:
					l[j] += 1
		c = 0
		for i in range(n - 1, 1, -1):
			for j in range(i - 1, 0, -1):
				if arr[i] > arr[j]:
					c += l[j]
		return c


class Solution:

	def countTriplets(self, nums):
		n = len(nums)
		left_less = 0
		right_more = 0
		count = 0
		for i in range(1, n - 1):
			left_less = sum((1 for num in nums[:i] if num < nums[i]))
			right_more = sum((1 for num in nums[i + 1:] if num > nums[i]))
			count += left_less * right_more
		return count


class Solution:

	def countTriplets(self, nums):
		if len(nums) < 3:
			return 0
		ans = 0
		n = len(nums)
		for i in range(1, n - 1):
			sma = 0
			for j in range(i - 1, -1, -1):
				if nums[i] > nums[j]:
					sma += 1
			la = 0
			for j in range(i + 1, n):
				if nums[i] < nums[j]:
					la += 1
			ans += sma * la
		return ans


from sortedcontainers import SortedList as SL
from functools import reduce

class Solution:

	def countTriplets(self, nums):
		n = len(nums)
		(f, b) = ([0] * n, [0] * n)
		sl = SL()
		for (i, val) in enumerate(nums):
			sl.add(val)
			f[i] = sl.bisect_left(val)
		sl = SL()
		for (i, val) in list(enumerate(nums))[::-1]:
			sl.add(-val)
			b[i] = sl.bisect_left(-val)
		return sum([x[0] * x[1] for x in zip(f, b)])


class Solution:

	def leri(self, i, nums):
		(left, right) = (0, 0)
		for j in range(0, i):
			if nums[j] < nums[i]:
				left += 1
		for j in range(i + 1, len(nums)):
			if nums[j] > nums[i]:
				right += 1
		return [left, right]

	def countTriplets(self, nums):
		(left, right) = ([], [])
		for i in range(len(nums)):
			k = self.leri(i, nums)
			left.append(k[0])
			right.append(k[1])
		c = 0
		for i in range(1, len(nums) - 1):
			c += left[i] * right[i]
		return c


class Solution:

	def countTriplets(self, A):
		N = len(A)
		ans = 0
		for i in range(1, N - 1):
			l = 0
			for j in range(i - 1, -1, -1):
				if A[j] < A[i]:
					l += 1
			r = 0
			for j in range(i + 1, N):
				if A[j] > A[i]:
					r += 1
			ans += l * r
		return ans


class Solution:

	def countTriplets(self, nums):
		ans = 0
		N = len(nums)
		for i in range(1, N - 1):
			left = sum((1 for j in range(i) if nums[j] < nums[i]))
			right = sum((1 for j in range(i + 1, N) if nums[i] < nums[j]))
			ans += left * right
		return ans


class Solution:

	def countTriplets(self, nums):
		count = 0
		for index in range(1, len(nums) - 1):
			left_count = 0
			right_count = 0
			for i in range(0, index):
				if nums[i] < nums[index]:
					left_count += 1
			for j in range(index + 1, len(nums)):
				if nums[j] > nums[index]:
					right_count += 1
			count += left_count * right_count
		return count


class Solution:

	def countTriplets(self, nums):
		a = 0
		for i in range(len(nums)):
			left = 0
			right = 0
			for j in range(i + 1, len(nums)):
				if nums[j] > nums[i]:
					right += 1
			for k in range(i):
				if nums[k] < nums[i]:
					left += 1
			a += left * right
		return a


class Solution:

	def countTriplets(self, nums):
		if len(nums) < 3:
			return 0
		ans = 0
		for i in range(len(nums)):
			smaller = 0
			for j in range(i - 1, -1, -1):
				if nums[j] < nums[i]:
					smaller += 1
			larger = 0
			for k in range(i + 1, len(nums)):
				if nums[k] > nums[i]:
					larger += 1
			ans += smaller * larger
		return ans


class Solution:

	def countTriplets(self, nums):
		ans = 0
		for i in range(1, len(nums)):
			(a, b) = (0, 0)
			for j in range(i):
				if nums[j] < nums[i]:
					a += 1
			for k in range(i, len(nums)):
				if nums[k] > nums[i]:
					b += 1
			ans += a * b
		return ans


class Solution:

	def countTriplets(self, nums):
		ans = 0
		for i in range(1, len(nums)):
			lT = 0
			gT = 0
			for j in range(i):
				if nums[j] < nums[i]:
					lT += 1
			for k in range(i, len(nums)):
				if nums[k] > nums[i]:
					gT += 1
			ans += gT * lT
		return ans


class Solution:

	def countTriplets(self, nums):
		sum_count = 0
		for j in range(1, len(nums) - 1):
			(count_a, count_b) = (0, 0)
			for i in range(j - 1, -1, -1):
				if nums[i] < nums[j]:
					count_a += 1
			for k in range(j + 1, len(nums)):
				if nums[k] > nums[j]:
					count_b += 1
			sum_count += count_a * count_b
		return sum_count


class Solution:

	def countTriplets(self, nums):

		def countleft(arr, i):
			count = 0
			for val in arr[:i + 1]:
				if val < arr[i]:
					count += 1
			return count

		def countright(arr, i):
			count = 0
			for val in arr[i:]:
				if val > arr[i]:
					count += 1
			return count
		res = 0
		for i in range(len(nums)):
			res += countleft(nums, i) * countright(nums, i)
		return res


class Solution:

	def countTriplets(self, nums):
		n = len(nums)
		ans = 0
		if n < 3:
			return 0
		for i in range(1, n - 1):
			small = 0
			large = 0
			for j in range(i):
				if nums[j] < nums[i]:
					small += 1
			for k in range(i + 1, n):
				if nums[k] > nums[i]:
					large += 1
			ans += large * small
		return ans


class Solution:

	def countTriplets(self, nums):
		total = 0
		for j in range(len(nums)):
			cntLeft = 0
			cntRight = 0
			for i in range(j):
				if nums[i] < nums[j]:
					cntLeft += 1
			for k in range(j + 1, len(nums)):
				if nums[k] > nums[j]:
					cntRight += 1
			total += cntLeft * cntRight
		return total


class Solution:
	l = []
	m = []

	def countTriplets(self, nums):
		n = len(nums)
		self.l = [0 for i in range(n)]
		self.m = [0 for i in range(n)]
		if n == 1 or n == 2:
			return 0
		for i in range(n):
			num = nums[i]
			a = 0
			for j in range(0, i):
				if nums[j] < num:
					a += 1
			self.l[i] = a
		for i in range(n - 1, -1, -1):
			num = nums[i]
			a = 0
			for j in range(n - 1, i, -1):
				if nums[j] > num:
					a += 1
			self.m[i] = a
		ans = 0
		for i in range(0, n):
			ans += self.l[i] * self.m[i]
		return ans


class Solution:

	def countTriplets(self, nums):

		def countleft(indx):
			count = 0
			for i in range(indx):
				if nums[i] < nums[indx]:
					count += 1
			return count

		def countright(indx, n):
			count = 0
			for i in range(indx + 1, n):
				if nums[indx] < nums[i]:
					count += 1
			return count
		n = len(nums)
		ans = 0
		for indx in range(n):
			ans += countleft(indx) * countright(indx, n)
		return ans


class Solution:

	def countTriplets(self, nums):
		ans = 0
		n = len(nums)
		if n > 2:
			for i in range(1, n - 1):
				(left, right) = (0, 0)
				for j in range(n):
					if j < i and nums[j] < nums[i]:
						left += 1
					elif j > i and nums[j] > nums[i]:
						right += 1
				if left == 0 or right == 0:
					continue
				else:
					ans += left * right
		return ans


class Solution:

	def countTriplets(self, nums):
		count = 0
		n = len(nums)
		for j in range(n - 1):
			(l, r) = (0, 0)
			i = 0
			k = j + 1
			while i < j:
				if nums[i] < nums[j]:
					l += 1
				i += 1
			while k < n:
				if nums[j] < nums[k]:
					r += 1
				k += 1
			count += l * r
		return count


class Solution:

	def countTriplets(self, a):
		r = len(a)
		c = 0
		for i in range(1, r):
			lres = 0
			rres = 0
			for j in range(i):
				if a[j] < a[i]:
					lres += 1
			for j in range(i + 1, r):
				if a[j] > a[i]:
					rres += 1
			c += lres * rres
		return c


class Solution:

	def countTriplets(self, nums):
		A = nums
		N = len(A)
		if N < 3:
			return 0
		rh = [0] * (N - 1)
		rh[N - 2] = 1 if A[N - 2] < A[N - 1] else 0
		rh[N - 3] = (1 if A[N - 3] < A[N - 2] else 0) + (1 if A[N - 3] < A[N - 1] else 0)
		ans = 0
		for i in range(N - 3, -1, -1):
			rh[i] = 1 if A[i] < A[N - 1] else 0
			for j in range(i + 1, N - 1):
				if A[i] >= A[j]:
					continue
				rh[i] += 1
				ans += rh[j]
		return ans


class Solution:

	def countTriplets(self, nums):
		c = 0
		s = 0
		l = 0
		for i in range(0, len(nums)):
			for j in range(i):
				if nums[i] > nums[j]:
					s += 1
			for j in range(i + 1, len(nums)):
				if nums[i] < nums[j]:
					l += 1
			c += s * l
			s = 0
			l = 0
		return c


class Solution:

	def countTriplets(self, nums):
		count = 0
		n = len(nums)
		st = 0
		while st < n:
			(left, right) = (0, 0)
			cur = nums[st]
			for i in range(st):
				if nums[i] < cur:
					left += 1
			for i in range(st + 1, n):
				if nums[i] > cur:
					right += 1
			count += left * right
			st += 1
		return count


class Solution:

	def countTriplets(self, nums):
		N = len(nums)
		ansl = [0] * N
		ansr = [0] * N
		ansl[0] = 0
		for i in range(1, N):
			count = 0
			for j in range(0, i):
				if nums[j] < nums[i]:
					count += 1
			ansl[i] = count
		ansr[N - 1] = 0
		for i in range(N - 2, 0, -1):
			count = 0
			for j in range(i + 1, N):
				if nums[j] > nums[i]:
					count += 1
			ansr[i] = count
		ans = 0
		for i in range(0, N):
			ans += ansl[i] * ansr[i]
		return ans


class Solution:

	def countTriplets(self, nums):
		f = 0
		for j in range(1, len(nums) - 1):
			c = 0
			w = 0
			for k in range(j + 1, len(nums)):
				if nums[j] < nums[k]:
					c += 1
			for i in range(0, j):
				if nums[j] > nums[i]:
					w += 1
			f = f + c * w
		return f


from itertools import combinations

class Solution:

	def countTriplets(self, nums):
		return sum((sum((n < num for n in nums[:index + 2])) * sum((n > num for n in nums[index + 1:])) for (index, num) in enumerate(nums[1:-1])))


class Solution:

	def countTriplets(self, nums):
		cnt = 0
		for i in range(1, len(nums) - 1):
			cnt1 = 0
			for j in range(i - 1, -1, -1):
				if nums[j] < nums[i]:
					cnt1 += 1
			cnt2 = 0
			for k in range(i + 1, n):
				if nums[k] > nums[i]:
					cnt2 += 1
			cnt += cnt1 * cnt2
		return cnt


class Solution:

	def countTriplets(self, nums):
		ans = 0
		for j in range(1, len(nums) - 1):
			(s, g) = (0, 0)
			for i in range(j - 1, -1, -1):
				if nums[i] < nums[j]:
					s += 1
			for i in range(j + 1, len(nums)):
				if nums[j] < nums[i]:
					g += 1
			ans += s * g
		return ans


class Solution:

	def countTriplets(self, nums):
		count = 0
		N = len(nums)
		for i in range(N):
			R = 0
			L = 0
			for j in range(i - 1, -1, -1):
				if nums[i] > nums[j]:
					R += 1
			for j in range(i + 1, N):
				if nums[i] < nums[j]:
					L += 1
			count += R * L
		return count


class Solution:

	def countTriplets(self, a):
		ans = 0
		n = len(a)
		for j in range(1, n):
			cnt = 0
			i = j - 1
			while i >= 0:
				if a[i] < a[j]:
					cnt += 1
				i -= 1
			large = 0
			for k in range(j + 1, n):
				if a[k] > a[j]:
					large += 1
			ans += cnt * large
		return ans