Last Updated: 16 Dec, 2020

Count Triplets in sorted DLL

Moderate

Asked in company

Solve now

Problem statement

You are given a sorted doubly linked list and an integer value x. Your task is to count the number of triplets in the doubly linked list whose sum is equal to x.

Input format :

The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

Then the T test cases follow.

The first line of every test case contains the elements of the doubly linked list  separated by a single space and terminated by -1. Hence, -1 would never be a list element.

The second line of every test case contains the value of x.

Output Format :

For each test case, print the count of triplets.

The output of each test case is printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
3 <= N <= 100
-10^8 <= data <= 10^8 and data != -1
-3*10^8 <= x <= 3*10^8
Where T is the number of test cases, N is the length of the doubly linked list and x is the given value of the sum.

Solve now

Approaches

01 Approach

The simplest way is to go through all the possible triplets and incrementing count by 1 whenever any desired triplet is found.

Algorithm:

Take three nested loops to iterate the whole list.
For every possible triplet check whether it sums up to the given value x, if yes increment the count by 1 and iterate further.
Return the value of count.

Solve now

02 Approach

It is given that the doubly linked list is sorted, we can use this property by applying the two pointer approach. The idea is to traverse the doubly linked list from left to right, and for each current node during the traversal, initialize two pointers first and last. The first pointer will be pointing to the node just next to the current node and the last pointer will be pointing to the end node of the linked list. Count the pairs, using these two pointers, whose sum is equal to ‘x - current node’s data’ and add this count to the total count of triplets. Return the total count.

Algorithm:

Traverse the doubly linked list.
Take two pointers first and last pointing to the next node of the current node and the last node of the list respectively.
Add the data of the first and the last node and save it in a variable say pairSum. If ‘x - pairSum’ is greater than 0 move the first node to its next node and if its value is less than 0 then move the last node to its previous node .
Increment the total count by 1 if any triplet whose sum is x is found.
Return the value of the total count.

Solve now