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!