Last Updated: 13 Nov, 2020
Count Triplets
Easy
Asked in companies
You have been given an integer ‘X’ and a non-decreasing sorted doubly linked list with distinct nodes.
Your task is to return the number of triplets in the list that sum up to the value ‘X’.
Input format :
The first line contains a single integer ‘T’ denoting the number of test cases. The test cases follow.
The first line of each test case contains a single integer ‘X’.
The second line of the input 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.
Output Format:
For each test case, print in a new line a single integer denoting the number of triplets that have the sum equal to ‘X’.
Note:
You don’t need to print anything; it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 5
1 <= N <= 10 ^ 3
- 3 * 10 ^ 5 <= X <= 3 * 10 ^ 5
- 10 ^ 5 <= data <= 10 ^ 5 and data != - 1
Where ‘N’ is the number of nodes in the given linked list, and ‘X’ is the required triplet sum value.
Time limit: 1 sec
Approaches
The idea is to explore all the triplets and count those triplets which have a sum equal to ‘X’. We will use a variable 'COUNT' which will be initialized to 0, to count the number of triplets with sum ‘X’. The steps are as follows:
- We will iterate the linked list and pick each node one by one and pivot that node as the first element of the triplet, let this node be 'FIRSTPTR'.
- For the second element of the triplet, iterate from the next node of 'FIRSTPTR' till the end of the linked list and one by one pick each node and pivot that, let’s say this node is 'SECONDPTR'. So we will pivot 'SECONDPTR' as the second element of the triplet.
- For the third element, iterate from the next node of 'SECONDPTR' till the end of the list and pivot each node as the third element.
- If the sum of the three pivoted nodes is equal to ‘X’ increment 'COUNT' by 1.
The idea is to store nodes that have been explored in the HashSet so that we can effectively check if any particular node exists in the doubly linked list or not and then explore all possible pairs of nodes and then find the third node using the HashSet. We will use a variable 'COUNT' which will be initialized to 0, to count the number of triplets with sum ‘X’.
The steps are as follows:
- Pick each node one by one and pivot that node, let’s say this node is 'FIRSTPTR' and the data of this node is ‘FIRSTVAL’.
- For the second node, start exploring from the next node of 'FIRSTPTR' till the end of the doubly linked list and one by one pick each node as a pivot, let’s say this node is ‘SECONDPTR’ and data of this node is ‘SECONDVAL’.
- Now check if the HashSet contains the value (X - (FIRSTVAL + SECONDVAL)) or not. If it contains the value (X - (FIRSTVAL + SECONDVAL)) increment count by one.
- Insert the data of 'FIRSTPTR' into the HashSet.
Since the given doubly linked list is sorted, we can pivot one element, and then we can use the two-pointer technique. We will use a variable 'COUNT' which will be initialised to 0, to count the number of triplets with sum ‘X’.
The algorithm looks like:
- We will iterate through the linked list and pick each node one by one and pivot that node as the first element of the triplet, let this node be 'PTR' and data of this node is ‘VAL’.
- Now initialise two pointers to find a pair of elements in the sorted doubly linked list which has the sum of (X - val). Let’s say the first pointer is 'START' and the second pointer is 'END'.
- Initialise 'START' as the next node after 'PTR' of the doubly linked list and 'END' as the last node of the doubly linked list. Here we don’t have random access property, so we will store the last node of the doubly linked list once in the beginning by traversing the entire list.
- If the sum of data at the 'START' node and 'END' node is less than (X - val), then we want to increase the sum so we will move the 'START' pointer forward to get a larger value node.
- If the sum of data at the 'START' node and 'END' node is greater than (X - val), then we want to decrease the sum so we will move the 'END' pointer backwards to get a smaller value node.
- If the sum of data at the 'START' node and 'END' node is equal to (X - val), then we found a valid triplet and increment count by 1. We will move the 'START' pointer forward to get a larger value node because all the smaller value nodes have been explored, and we will move the 'END' pointer backwards to get a smaller value node because all the greater value nodes have been explored.
- Loop will terminate when either of 'START' or 'END' become NULL, or when they cross each other, i.e. (END -> next == START OR END == START).