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

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

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.

Problem Statement Understanding

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 the sum equal to 15. Rest all the possible triplets have 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

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: O(N3), Since we are using three nested loops to count triplet combinations.
Space complexity: 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

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 triplet having sum equal to x has been counted 3 times during the above process.

Algorithm 2

  • 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: O(N2), Since we have traversed through the linked list twice for every Element.
Space Complexity: 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 next approach.

Approach 3

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

  • 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

Code Implementation

#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(N2), 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 are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post How To Write C Functions That Modify The Head Pointer Of A Linked List
Next post Clone a linked list with next and random pointer in O(1) space

Leave a Reply

Your email address will not be published. Required fields are marked *