Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Example
2.
Approach 1: Brute Force 
2.1.
Algorithm
2.2.
Implementation in C++
2.2.1.
Complexity Analysis
3.
Approach 2: Using Hash-map
3.1.
Algorithm
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Approach 3: Optimized Approach using two pointer
4.1.
Algorithm
4.2.
Implementation in C++
4.2.1.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
Why is the time complexity of deletion of elements from the mid O(1) in DLL?
5.2.
What is a memory-efficient doubly linked list? 
5.3.
What is a circular linked list?
5.4.
Distinguish between a linked list and a doubly-linked list? 
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Count triplets in a sorted Doubly Linked List whose sum is equal to a given value x

Author Prerna Tiwari
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

A Doubly Linked List is a type of linked list that contains a pointer to the next as well as the previous node in the sequence. A node in a doubly-linked list thus has three parts:

  • Node data
  • A pointer to the next node in sequence (next pointer)
  • A pointer to the previous node (previous pointer)

A Doubly Linked List is a linked list that allows for easy forward and backward navigation because it has an extra pointer that points to the previous node.

 

       Representation of Doubly linked list

Problem Statement

Given a sorted doubly linked list of distinct nodes (no two nodes contain the same data) and the value X. Count the number of triplets in the list that add up to X.

Example

Let us take the following linked list as input:

 

1 . head → 1 ←→ 2 ←→ 3 ←→ 4

If the desired sum is 9, from the linked list, we can see that there is only one possible triplet (2,3,4), which has a sum equal to 9. Rest all the possible triplets have a sum not equal to X.

 

2 . head → 1 ←→ 2 ←→ 3 ←→ 4 ←→ 5←→ 6 ←→ 8

 

If the desired sum is 15, from the linked list, we can see that there are only four possible triplets (8, 6, 1),(8, 6, 2),(8, 6, 3)

and (6, 4, 5), which have a sum equal to 15. Rest all the possible triplets have a sum not equal to X.

Hence our answer will be 4.

Approach 1: Brute Force 

This is the simplest and most common approach We will traverse the linked list using three nested loops, and for each triplet, we will check whether or not the triplet sums up to X:

Algorithm

  • Traverse the linked list using three nested loops to generate all possible triplets.
     
  • For each triplet, calculate the sum and check whether or not the triplet sums up to X.
     
  • If it does up to X, then this triplet combination should be counted.
     
  • Otherwise, continue.
     
  • Return the final count.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// structure of node of DLL
struct Node
{
    int data;
    struct Node *next, *prev;
};

void insert(struct Node **head, int data)
{
    // allocate node
    struct Node *temp = new Node();
    // put in the data
    temp->data = data;
    temp->next = temp->prev = NULL;

    if ((*head) == NULL)
        (*head) = temp;
    else
    {
        temp->next = *head;
        (*head)->prev = temp;
        (*head) = temp;
    }
}
// Driver code
int main()
{
    // start with an empty DLL
    struct Node *head = NULL;

    // insert data values in sorted order
    insert(&head, 12);
    insert(&head, 11);
    insert(&head, 10);
    insert(&head, 9);
    insert(&head, 8);
    insert(&head, 7);
    insert(&head, 4);
    int x = 19;

    // counting triplets using nested for loops
    struct Node *ptrs1, *ptrs2, *ptrs3;
    int counter = 0;
    // generate all possible triplets
    for (ptrs1 = head; ptrs1 != NULL; ptrs1 = ptrs1->next)
    {
        for (ptrs2 = ptrs1->next; ptrs2 != NULL; ptrs2 = ptrs2->next)
        {
            for (ptrs3 = ptrs2->next; ptrs3 != NULL; ptrs3 = ptrs3->next)
            {

                if ((ptrs1->data + ptrs2->data + ptrs3->data) == x)
                    // increment the count
                    counter++;
            }
        }
    }

    cout << "Count = " << counter << endl;
    return 0;
}

 

Input

12 11 10 9 8 7 4

 

Output

Count = 1

 

Complexity Analysis

Time Complexity

To count triplet combinations, we iterated over three nested loops.; therefore the time complexity is O(N3).

Space Complexity

Since we have not used extra space the space complexity will be O(1).

Also see, Rabin Karp Algorithm

Approach 2: Using Hash-map

The time complexity of the brute force approach is very large. Hence to optimize our code, we will try and use hashmap. The plan is to use a hashmap with a (key, value) pair as the key and a pointer to that node as the value to store the data.

Algorithm

  • Create every possible pair of nodes from the linked list. 
     
  • Calculate the sum of pair (sum of data in the two nodes) for each pair of nodes and see if (X-pair sum) exists in the hash table.
     
  • If it exists, check that the two nodes in the pair are not equal to the node associated with (X-pair sum) in the hash table before incrementing the count.
     
  • Finally, we will return (count / 3) as our output because each of our triplets with a sum equal to x has been counted three times during the calculation.

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// structure of node of DLL
struct Node
{
    int data;
    struct Node *next, *prev;
};

void insert(struct Node **head, int data)
{
    // allocate node
    struct Node *temp = new Node();
    // put in the data
    temp->data = data;
    temp->next = temp->prev = NULL;

    if ((*head) == NULL)
        (*head) = temp;
    else
    {
        temp->next = *head;
        (*head)->prev = temp;
        (*head) = temp;
    }
}

// Driver program to test above
int main()
{
    // start with an empty DLL
    struct Node *head = NULL;

    // insert data values in sorted order
    insert(&head, 12);
    insert(&head, 10);
    insert(&head, 8);
    insert(&head, 6);
    insert(&head, 4);
    insert(&head, 2);
    int x = 20;

    // counting triplets with sum equal to x
    struct Node *ptrs, *ptrs1, *ptrs2;
    int counter = 0;
    unordered_map<int, Node *> um;

    for (ptrs = head; ptrs != NULL; ptrs = ptrs->next)
        um[ptrs->data] = ptrs;

    // generate all possible pairs
    for (ptrs1 = head; ptrs1 != NULL; ptrs1 = ptrs1->next)
        for (ptrs2 = ptrs1->next; ptrs2 != NULL; ptrs2 = ptrs2->next)
        {
            int p_sum = ptrs1->data + ptrs2->data;
            if (um.find(x - p_sum) != um.end() && um[x - p_sum] != ptrs1 && um[x - p_sum] != ptrs2)
                // increment counter
                counter++;
        }
    counter /= 3;
    cout << "Count = "
         << counter << endl;
    return 0;
}

 

Input

12 10 8 6 4 2

 

Output

Count = 3

 

Complexity Analysis

Time Complexity

The time complexity would be O(N2) as we have traversed twice for every node i.e, we are using two nested loops. Here, N represents the length of the doubly linked list.

Space Complexity

Since we are using extra space in the form of a map, hence the space complexity will be O(N).

Approach 3: Optimized Approach using two pointer

This is a practical approach where we will be using two-pointers. The plan here is to traverse the linked list from left to right, counting the number of pairs in the list that have a sum equal to the value (X - Current Node's Data) for each node.

Algorithm

  • Make a variable called count and set its value to 0. This variable counts the total number of possible triplets in the linked list with sum X.
     
  • Using the pointer variable curr, begin traversing the linked list from the head node.
     
  • During traversal, initialize two pointers begin and end to the next node of the current node (curr->next) and the end node of the linked list, respectively.
     
  • Traverse till first and  second are not equal to NULL , first != second and second->next != first
     
  • Count the number of pairs in the list that have a sum equal to (X - currdata). Add the number of pairs to the number of variables. 

Implementation in C++

#include <bits/stdc++.h>

using namespace std;

// structure of node of DLL
struct Node
{
    int data;
    struct Node *next, *prev;
};

int pairCounter(struct Node *node1, struct Node *node2, int d_value)
{
    int count = 0;

    while (node1 != NULL && node2 != NULL &&
           node1 != node2 && node2->next != node1)
    {

        // pair found
        if ((node1->data + node2->data) == d_value)
        {

            // increment counter
            count++;

            // move node1 in forward direction
            node1 = node1->next;

            // move node2 in backward direction
            node2 = node2->prev;
        }

        // if sum is greater than 'd_value'
        // move node2 in backward direction
        else if ((node1->data + node2->data) > d_value)
            node2 = node2->prev;

        // else move node1 in forward direction
        else
            node1 = node1->next;
    }

    // required count of pairs
    return count;
}

// A utility function
void insert(struct Node **head, int data)
{
    // allocate node
    struct Node *temp = new Node();

    // put in the data
    temp->data = data;
    temp->next = temp->prev = NULL;

    if ((*head) == NULL)
        (*head) = temp;
    else
    {
        temp->next = *head;
        (*head)->prev = temp;
        (*head) = temp;
    }
}

// Driver code
int main()
{

    struct Node *head = NULL;

    // insert data values in sorted order
    insert(&head, 9);
    insert(&head, 8);
    insert(&head, 6);
    insert(&head, 4);
    insert(&head, 3);
    insert(&head, 2);
    insert(&head, 2);

    int x = 12;

    // Counting triplets in a sorted Doubly Linked List whose sum is equal to a given value x

    struct Node *current, *node1, *node2;
    int count = 0;

    // get pointer to the node2 node of
    // the doubly linked list
    node2 = head;
    while (node2->next != NULL)
        node2 = node2->next;

    // traversing the doubly linked list
    for (current = head; current != NULL; current = current->next)
    {

        // for each current node
        node1 = current->next;

        count += pairCounter(node1, node2, x - current->data);
    }

    cout << "Count = "
         << count << endl;
    return 0;
}

 

Input

9 8 6 4 3 2 2

 

Output

Count = 3

 

Complexity Analysis

Time Complexity

The time complexity would be O(N2) because we have traversed twice for every node i.e, we are using two nested loops. Here, N represents the length of the doubly linked list.

Space Complexity

Since we have not used extra space the space complexity will be O(1).

Frequently Asked Questions

Why is the time complexity of deletion of elements from the mid O(1) in DLL?

Deletion of elements from the mid is O(1) in DLL because, in this case, one does not have to traverse the whole array to adjust the previous and next links, which is not in the case of a singly linked list.

What is a memory-efficient doubly linked list? 

When each node has only one pointer to traverse the list back and forth.  

What is a circular linked list?

Circular Linked List is a singly Linked List, where the last node of a singly Linked List contains a pointer to a node that points to the first node (head node) of the Linked List.

Distinguish between a linked list and a doubly-linked list? 

The elements of a singly linked list can only be traversed in one direction. A doubly linked list provides for two-way traversal of elements. Because a singly linked list only stores the pointer to one node, it uses less memory. However, a doubly-linked list consumes extra memory per node (due to the two pointers).

Conclusion

In this article, We discussed the problem of counting the triplets in a sorted Doubly Linked List whose sum is equal to a given value x. We started with introducing the doubly linked list after that we discussed the problem statement with the help of examples of the problem count triplets in a sorted Doubly Linked List. We have also seen the implementation of the problem with three different approaches, and in the end, we have concluded with the time complexity and space complexity of all the approaches.

We hope that this blog has helped you enhance your knowledge regarding the problem to count triplets in a sorted Doubly Linked List whose sum is equal to a given value x if you would like to learn more, check out our other articles on doubly linked list.

To study more about Linked Lists, refer to Applications Of Linked Lists.

For peeps out there who want to learn more about Data Structures, Algorithms, Power programming, JavaScript, or any other upskilling, please refer to guided paths on Coding Ninjas Studio. Enroll in our courses, go for mock tests, solve problems available, and interview puzzles. Also, you can put your attention towards interview stuff- interview experiences and an interview bundle for placement preparations. 

Do upvote our blog to help other ninjas grow. 

Happy Coding!

Live masterclass