Count Triplet Efficient Code

In this class, We discuss Count Triplet Efficient Code.

For Complete YouTube Video: Click Here

The reader should have basic coding skills.

Take our placement training for service-based companies course to improve basic coding skills. Click Here.

Given N distinct elements.

Example:

[1,6,5,7]

We have to find all the triplets of form 1 + 6 = 7

Another triplet 1 + 5 = 6

Total two triplets are formed.

Identify the count of the number of triplets.

Time Complexity: O(n^2)

Space Complexity: O(1)

First Way:

We use a nested loop three-level.

for i = 0 to n

for j = 0 to n except i

for k = 0 to n except i, j

0(n^3) is the time complexity using three nested loops.

Using the three nested loops, we are checking all the possible triplets.

Second Way:

Given elements [8,1,2,4,3,7,5,6]

First, we need to sort the elements.

[1,2,3,4,5,6,7,8]

To sort the elements we take O(nlogn) time.

Take the maximum element 8 and check the possibilities of triplets of 8.

We need to check the elements that are less than 8.

We take the variables i, j, and k.

The variable i points to 8. and i points to least element and j points to 7.

Now check the conditions.

if a[i] + a[j] = a[k]

i++

j–

else if a[i] > a[j] + a[k]

i++

else

j–

Repeat the process for all the elements from last to first.

Each iteration works for n times and is repeated n times. so time O(n^2)

Total Time complexity O(nlogn) + O(N^2)

We take the highest polynomial, so the time complexity is O(n^2).

Program:

def countTriplet(arr, n):

   count=0

   arr.sort()

   i = n-1

   while(i >= 0):

       j = 0

       k = i – 1

       while (j < k):

           if (arr[i] == arr[j] + arr[k]):

               count+=1

               j+=1

               k-=1

           elif (arr[i] > arr[j] + arr[k]):

               j += 1

           else:

               k -= 1

       i -= 1

   return count

n = int(input(“enter n value”))

arr=[]

for i in range(n):

   x=int(input())

   arr.append(x) 

val=countTriplet(arr,n)