Count triplets in a sorted doubly linked list whose sum is equal to a given value X

Last Updated on November 25, 2022 by Prepbytes

As we have already seen many articles on doubly linked lists, let’s take another question in which we have to count triplets in a sorted doubly linked list whose sum is equal to a given value x, A doubly linked list contains an extra pointer called the previous pointer which stores the address of the previous node.
So let us give a look at the problem statement of count triplets in a sorted doubly linked list whose sum is equal to a given value x.

How to count triplets in a sorted doubly linked list whose sum is equal to a given value x

Given a sorted doubly linked list of distinct nodes (No two nodes have the same data) and a value X. Count triplets in the list that sum to a given value X.

Let’s try to understand the problem statement with the help of some examples.
According to the problem statement, we are given a sorted doubly linked list and a value X. We have to count all the triplets from this doubly linked list which have a sum equal to X.
If the doubly linked list is: head → 2 ←→ 3 ←→ 5 ←→ 7 ←→ 10 ←→ 13 and X = 15.

• From the linked list, we can see that there are only two possible triplets (2, 3, 10) and (3, 5, 7), which have a sum equal to 15. Rest all the possible triplets have a sum not equal to X.
• So our count of triplets will be 2.

If the doubly linked list is: head → 1 ←→ 2 ←→ 3 ←→ 4 ←→ 5 and X = 9.

• In this case, out of all the possible triplets, the triplets with the sum equal to 9 will be (1, 3, 5), (2, 3, 4).
• So our count of triplets will be 2.

Some more examples

Sample Input 1 : head → 1 ←→ 2 ←→ 3 ←→ 4,  X = 5
Sample Output 1: 0

There do not exist any triplet with sum equal to 5.

Sample Input 2: head → 1 ←→ 3 ←→ 5 ←→ 7 ←→ 9 ←→ 11, X = 15
Sample Output 2: 3

The triplets are (1, 3, 11), (3, 5, 7), (1, 5, 9).

Now I think from the above examples, the problem statement is clear. So let’s see how we will approach it. Any Ideas?

• If not, it’s okay. We will see in the next section thoroughly how we can approach this problem.

Let’s move to the approach section.

Approach 1 of count triplets in a sorted doubly linked list whose sum is equal to a given value x

Our naive approach will be to traverse the linked list using three nested loops, and while traversing, for every triplet, we will check whether the triplet sums up to X or not:

• If it does sum up to X, then count this triplet combination.
• Else continue with the loops.

Time complexity of count triplets in a sorted doubly linked list whose sum is equal to a given value x : O(N³), Since we are using three nested loops to count triplet combinations.

Space complexity of count triplets in a sorted doubly linked list whose sum is equal to a given value x : O(1), As no extra space is used.

Next, we will see how we can reduce this complexity. Any ideas?

• If not, it’s okay. We will see in the next section how we can reduce the time complexity.

Let’s move to a comparatively better approach than approach 1.

Approach 2 of count triplets in a sorted doubly linked list whose sum is equal to a given value x

The idea is to create a hashmap with (key, value) pair to store the node’s data as the key and a pointer to that node as the value.

Now, generate each possible pair of nodes from the linked list. For each pair of nodes, calculate the pair_sum(sum of data in the two nodes) and check whether (X-pair_sum) exists in the hash table or not.

• If it exists, then also verify that the two nodes in the pair are not the same as the node associated with (X-pair_sum) in the hash table and finally increment the count.

• Finally, we will be returning (count / 3) as our output as each of our triplets having sum equal to x has been counted 3 times during the above process.

Algorithm 2 of count triplets in a sorted doubly linked list whose sum is equal to a given value x

• Initialize the count to zero.
• Now traverse through the linked list and store the node’s data as a key and a pointer to that node as the value in a map.

• Further, iterate over the linked list using two nested loops in which the first loop iterates from head to NULL using ptr1, and the second nested loop iterates from the next node of pointer of first loop (ptr1->next) to NULL.

  • Now in the variable pair_sum, stores the sum of data of two pointers, i.e., ptr1->data + ptr2->data.
  • Now check if the map contains (X – pair_sum) and also check if the two nodes in the pair are not the same as the node associated with a value (X-pair_sum) in the map.
  • Now, if the condition satisfies, increment the count.
• Finally, we have to return (count / 3) as our output because each triplet has been counted 3 times during the above process.

Time Complexity count triplets in a sorted doubly linked list whose sum is equal to a given value x: O(N²), Since we have traversed through the linked list twice for every Element.

Space Complexity of count triplets in a sorted doubly linked list whose sum is equal to a given value : O(N), No extra space used.

Now we can see that this approach is far better than the previous approach, but we are also using extra space here. So next, we will try to see if we can somehow reduce the space complexity. Any Ideas?

• If not, it’s okay. We will see in the next approach how we can do this in less space complexity.

Let’s move to the next approach.

Approach 3 of count triplets in a sorted doubly linked list whose sum is equal to a given value x

This approach is an efficient one. Here the idea is to traverse the linked list from left to right, and for each node, count number of pairs in the list that sum up to the value (X – Current Node’s Data).

Let’s see the algorithm.

Algorithm 3 of count triplets in a sorted doubly linked list whose sum is equal to a given value x

• Create a count named variable and initialize it to 0. This count variable will keep track of the total number of possible triplets in the linked list having sum X.

• Start traversing the linked list from the head node using a pointer variable curr.

• During traversal for each node, initialize two pointers begin and end to next of current node (curr->next) and end node of linked list respectively.

• Count the number of pairs in list from begin to end having sum equal to (X – curr→data). Add the count of pairs to the variable count. Please visit the following article to see how we can find the pairs in a doubly linked list having a certain sum Check out this article.

• Finally, after the traversal is over, the count variable will have the count of all possible triplets having sum equal to X.

Dry Run of count triplets in a sorted doubly linked list whose sum is equal to a given value x

Code Implementation of count triplets in a sorted doubly linked list whose sum is equal to a given value x

#include 
using namespace std;

/* Node structure of the doubly linked-list*/
struct Node {
    int data;
    struct Node* next, *prev;
};

/* Using this function we will count the number of pairs having sum equal to given the given value */
int countValpairs(struct Node* begin, struct Node* end, int value)
{
    int count = 0;
    while (begin != NULL && end != NULL && begin != end && end->next != begin) {
        
        if ((begin->data + end->data) == value) {
            count++;
            begin = begin->next;
            end = end->prev;
        }
        
        else if ((begin->data + end->data) > value){
            end = end->prev;
        }
        
        else{
            begin = begin->next;
        }
    }
    return count;
}

/* Using this function we will count the number of triplets in a list having sum equal to X */
int countXtriplets(struct Node* head, int X)
{
    if (head == NULL){
        return 0;
    }
    struct Node* current, *first, *last;
    int count = 0;
    
    last = head;
    while (last->next != NULL){
        last = last->next;
    }
    
    for (current = head; current != NULL; current = current->next) {
        first = current->next;
        count += countValpairs(first, last, X - current->data);
    }

    return count;
}

/* Using this function we will add a new node at the beginning of doubly linked list */
void insertAtHead(struct Node** head, int data)
{
    struct Node* temp = new Node();
    temp->data = data;
    temp->next = temp->prev = NULL;
    
    if ((*head) == NULL){
        (*head) = temp;

    }else{

        temp->next = *head;
        (*head)->prev = temp;
        (*head) = temp;
    }
}

int main()
{
    struct Node* head = NULL;
    insertAtHead(&head, 5);
    insertAtHead(&head, 4);
    insertAtHead(&head, 3);
    insertAtHead(&head, 2);
    insertAtHead(&head, 1);
    
    int X = 9;
    
    cout << "Count of triplets having sum equal to "<

						 

Output
Count of triplets having sum equal to 9 is 2

Time Complexity: O(N²), Since we have traversed through the linked list twice for every element.

So, In this blog, we have learned How to count triplets in a sorted doubly linked list whose sum is equal to a given value x. If you want to solve more questions on Linked List, which is curated by our expert mentors at PrepBytes, you can follow this link Linked List.

FAQs

1. What are the types of a linked lists?
The linked lists are of 4 types:

• Singly-linked lists
• Doubly linked lists
• Circular linked lists
• Circular doubly linked lists

2. What is a triplet?
A triplet is a tuple of three different elements from other indexes for example i, j, k.

3. What is an ordered list?
The ordered list is a collection of items in which the order of the items matters.