Given an array arr[] of distinct integers of size N and a value sum, the task is to find the count of triplets (i, j, k), having (i<j<k) with the sum of (arr[i] + arr[j] + arr[k]) smaller than the given value sum.
Example 1:
Input: N = 4, sum = 2
arr[] = {-2, 0, 1, 3}
Output:  2
Explanation: Below are triplets with 
sum less than 2 (-2, 0, 1) and (-2, 0, 3). 
 
Example 2:
Input: N = 5, sum = 12
arr[] = {5, 1, 3, 4, 7}
Output: 4
Explanation: Below are triplets with 
sum less than 12 (1, 3, 4), (1, 3, 5), 
(1, 3, 7) and (1, 4, 5).
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function countTriplets() that take array arr[], integer N  and integer sum as parameters and returns the count of triplets.
Expected Time Complexity: O(N^{2}).
Expected Auxiliary Space: O(1).
Constraints:
3 ≤ N ≤ 10^{3}
-10^{3} ≤ arr[i] ≤ 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Amortized analysis

Starter code: class Solution:
    def countTriplets(self, arr, n, sumo):
        #code here

Solutions:
class Solution:

	def countTriplets(self, arr, n, sumo):
		arr.sort()
		c = 0
		for i in range(len(arr)):
			tar = sumo - arr[i]
			si = i + 1
			ei = n - 1
			while si <= ei:
				if arr[si] + arr[ei] < tar:
					c += ei - si
					si += 1
				else:
					ei -= 1
		return c


class Solution:

	def countTriplets(self, arr, N, sum):
		arr.sort()
		count = 0
		for i in range(N - 2):
			(first, last) = (i + 1, N - 1)
			while first < last:
				req = arr[i] + arr[first] + arr[last]
				if req >= sum:
					last -= 1
				else:
					count += last - first
					first += 1
		return count


class Solution:

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


class Solution:

	def countTriplets(self, arr, n, sumo):
		arr.sort()
		cnt = 0
		for i in range(n):
			start = i + 1
			end = n - 1
			while start < end:
				summ = arr[i] + arr[start] + arr[end]
				if summ < sumo:
					cnt += end - start
					start += 1
				else:
					end -= 1
		return cnt


class Solution:

	def countTriplets(self, arr, n, sumo):
		arr.sort()
		cnt = 0
		for i in range(n - 2):
			j = i + 1
			k = n - 1
			target_sum = sumo - arr[i]
			while j < k:
				res = arr[i] + arr[j] + arr[k]
				if res < sumo:
					cnt += k - j
					j += 1
				else:
					k -= 1
		return cnt


class Solution:

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


class Solution:

	def countTriplets(self, arr, n, sumo):
		arr.sort()
		ans = 0
		for i in range(n - 2):
			a = arr[i]
			l = i + 1
			r = n - 1
			while l < r:
				if arr[l] + arr[r] < sumo - a:
					ans += r - l
					l += 1
				else:
					r -= 1
		return ans


class Solution:

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


class Solution:

	def countTriplets(self, arr, n, sumo):
		arr = sorted(arr)
		cnt = 0
		for i in range(n - 2):
			l = i + 1
			r = n - 1
			while l < r:
				tmp = arr[i] + arr[l] + arr[r]
				if tmp < sumo:
					cnt += r - l
					l += 1
				else:
					r -= 1
		return cnt


class Solution:

	def countTriplets(self, arr, n, sumo):
		arr = sorted(arr)
		cnt = 0
		for i in range(n - 2):
			left = i + 1
			right = n - 1
			while left <= right:
				temp = arr[i] + arr[left] + arr[right]
				if temp < sumo:
					cnt += right - left
					left += 1
				else:
					right -= 1
		return cnt


class Solution:

	def countTriplets(self, arr, n, sumo):
		arr = sorted(arr)
		count = 0
		for i in range(n):
			left = i + 1
			right = n - 1
			while left < right:
				sum1 = arr[i] + arr[left] + arr[right]
				if sum1 < sumo:
					count = count + right - left
					left = left + 1
				else:
					right = right - 1
		return count


class Solution:

	def countTriplets(self, arr, n, sumo):
		arr.sort()
		ans = 0
		for i in range(n):
			a = i + 1
			b = n - 1
			while a < b:
				if arr[a] + arr[b] + arr[i] < sumo:
					ans += b - a
					a += 1
				else:
					b -= 1
		return ans


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def countTriplets(self, arr, n, sumo):
		arr.sort()
		count = 0
		for i in range(n - 2):
			l = i + 1
			h = n - 1
			s = sumo - arr[i]
			while l < h:
				if s <= arr[l] + arr[h]:
					h -= 1
				elif s > arr[l] + arr[h]:
					count += h - l
					l += 1
		return count


class Solution:

	def countTriplets(self, arr, n, sumo):
		c = 0
		arr.sort()
		for i in range(n - 2):
			l = i + 1
			r = n - 1
			while l < r:
				s = arr[i] + arr[l] + arr[r]
				if s < sumo:
					c += r - l
					l += 1
				else:
					r -= 1
		return c


class Solution:

	def countTriplets(self, a, n, s):
		c = 0
		a = sorted(a)
		for i in range(n):
			j = i + 1
			k = n - 1
			while j < k:
				if a[i] + a[j] + a[k] >= s:
					k = k - 1
				else:
					c += k - j
					j += 1
		return c


class Solution:

	def pair_sum(self, arr, start, end, sumo, a):
		(i, j) = (start, end)
		cnt = 0
		while i < j:
			curr_sum = a + arr[i] + arr[j]
			if arr[i] == a:
				i += 1
			elif arr[j] == a:
				j -= 1
			elif curr_sum < sumo:
				cnt += j - i
				i += 1
			else:
				j -= 1
		return cnt

	def countTriplets(self, arr, n, sumo):
		arr.sort()
		cnt = 0
		for i in range(n - 2):
			cnt += self.pair_sum(arr, i + 1, n - 1, sumo, arr[i])
		return cnt


class Solution:

	def countTriplets(self, arr, n, sumo):
		ans = 0
		arr = sorted(arr)
		for i in range(len(arr)):
			(l, r) = (i + 1, len(arr) - 1)
			while l < r:
				curr = arr[i] + arr[l] + arr[r]
				if curr >= sumo:
					r -= 1
				else:
					ans += r - l
					l += 1
		return ans


class Solution:

	def countTriplets(self, arr, n, sumo):
		arr.sort()
		count = 0
		for i in range(n - 2):
			start = i + 1
			end = n - 1
			while start < end:
				total = arr[i] + arr[start] + arr[end]
				if total < sumo:
					count += end - start
					start += 1
				else:
					end -= 1
		return count


class Solution:

	def countTriplets(self, arr, n, sumo):
		n = len(arr)
		if n <= 2:
			return 0
		arr.sort()
		ctr = 0
		for (idx, num) in enumerate(arr):
			(i, j) = (idx + 1, n - 1)
			while i < j:
				if arr[i] + arr[j] + num >= sumo:
					j -= 1
				else:
					ctr += j - i
					i += 1
		return ctr


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def countTriplets(self, arr, n, sumo):
		ans = 0
		arr.sort()
		for i in range(n):
			j = i + 1
			e = n - 1
			c = 0
			s = 0
			while j < e:
				if arr[i] + arr[j] + arr[e] >= sumo:
					e = e - 1
				else:
					c = c + (e - j)
					j = j + 1
			ans = ans + c
		return ans


class Solution:

	def countTriplets(self, arr, n, sumo):
		result = 0
		arr.sort()
		for i in range(n - 2):
			if i > 0 or arr[i] != arr[i - 1]:
				start = i + 1
				end = n - 1
				while start < end:
					if arr[i] + arr[start] + arr[end] >= sumo:
						end -= 1
					else:
						result += end - start
						start += 1
		return result


class Solution:

	def countTriplets(self, nums, n, sumo):
		n = len(nums)
		res = 0
		nums.sort()
		for i in range(n - 2):
			l = i + 1
			r = n - 1
			while l < r:
				sumA = nums[i] + nums[l] + nums[r]
				if sumA < sumo:
					res += r - l
					l += 1
				else:
					r -= 1
		return res


class Solution:

	def countTriplets(self, arr, n, sumo):
		arr.sort()
		cnt = 0
		for i in range(0, n - 2):
			need = sumo - arr[i]
			l = i + 1
			r = n - 1
			while l < r:
				csum = arr[l] + arr[r]
				if csum < need:
					cnt += r - l
					l += 1
				else:
					r -= 1
		return cnt


class Solution:

	def countTriplets(self, arr, n, s):
		c = 0
		arr.sort()
		for i in range(n - 2):
			(j, k) = (i + 1, n - 1)
			while j < k:
				if arr[i] + arr[j] + arr[k] >= s:
					k -= 1
				elif arr[i] + arr[j] + arr[k] < s:
					c += k - j
					j += 1
		return c


class Solution:

	def countTriplets(self, nums, n, s):
		c = 0
		n = len(nums)
		nums.sort()
		for i in range(n - 2):
			(j, k) = (i + 1, n - 1)
			while j < k:
				if nums[i] + nums[j] + nums[k] >= s:
					k -= 1
				else:
					c += k - j
					j += 1
		return c


class Solution:

	def countTriplets(self, arr, n, sumo):
		nums = sorted(arr)
		count = 0
		start = 0
		while start < len(nums):
			(sub_start, sub_end) = (start + 1, len(nums) - 1)
			while sub_start < sub_end:
				if nums[sub_start] + nums[sub_end] < sumo - nums[start]:
					count += sub_end - sub_start
					sub_start += 1
				else:
					sub_end -= 1
			start += 1
		return count


class Solution:

	def countTriplets(self, arr, n, target):
		i = 0
		arr.sort()
		count = 0
		while i < n - 2:
			j = i + 1
			k = n - 1
			while j < k:
				if arr[i] + arr[j] + arr[k] < target:
					count += k - j
					j += 1
				else:
					k -= 1
			i += 1
		return count


class Solution:

	def countTriplets(self, arr, n, sumo):
		cnt = 0
		arr.sort()
		for l in range(0, n):
			(i, j) = (l + 1, n - 1)
			while i < j:
				sum = arr[l] + arr[i] + arr[j]
				if sum < sumo:
					cnt += j - i
					i += 1
				else:
					j -= 1
		return cnt