Find Pairs With Given Sum In A Doubly Linked List

Last Updated on March 10, 2022 by Ria Pathak

Problem Statement

In this problem, we will be given a sorted doubly linked list and a target integer. We need to find and print the pairs whose sum is equal to the given target.

Note: The integer value inside each node is unique.

Problem Statement understanding:

The problem statement is quite straightforward; we need to print pairs whose sum is equal to the given target.

Let’s try to understand the problem with the help of an example:
If the list given to us is:

and the target = 14

• We can easily see that the pairs (2,12) and (4,10) both sum up to the given target of 14.
• So, we need to just print both these pairs as output.

At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

Brute Force Approach

A straightforward approach to solve this problem is to use nested for loops. Using the outer for loop, pick each node one by one, and then using the inner for loop traverse in the forward direction from the current node to find a second node in the linked list such that the sum of nodes is equal to target.

The time complexity of this approach is O(N²). N is the number of nodes in the linked list.

Although this above approach will work fine, but for longer linked lists having length >= 10⁴, it will give a time limit exceed error. So, now we will try to see some other approaches having less time complexity.

Before jumping onto the optimized approach, try to think about how you can optimize the current approach such that it can find pairs for longer linked lists.

• If stuck, no problem, we will thoroughly see the better approach in the next section.

Let’s move to the approach section.

Approach

• We will follow two pointer approach in which one pointer will point to the smallest node initially i.e., the first node, and the second one will point to the largest node i.e., the last node.
• Now, we will iterate till both the pointers do not meet each other.
• In every iteration, we will calculate the sum of nodes pointed by both the pointers.
• If the sum is equal to the target, that means we have found the pair, and we have to print it and move the first pointer and the second pointer one node forward and backward, respectively.
• If the sum is smaller than the target, then it means that we need to increase it to make it equal to the target. Since the list is sorted, so moving the first pointer forward will increase the sum.
• If the sum is larger than the target, then it means that we need to decrease it to make it equal to the target. Since the list is sorted, so moving the second pointer backward will decrease the sum.

Algorithm

1) Initialize two pointers left and right with the first and last node of the list.
2) Run a while loop till both left and right are not equal or adjacent to each other.
3) Calculate the sum of the nodes pointed by the left and the right pointers.

• If the sum equals the target, print both the numbers and move left and right by one node forward and backward, respectively.
• Else if the sum is less than the target, move left forward by one node.
• Else, move right backward by one node.

Dry Run

Code Implementation

#include 
using namespace std;

class Node
{
    public:
    int data;
    Node* next;
    Node* prev;
};

void add_at_begin(Node** head, int x){
    //create node of doubly linked list
    Node* new_node = new Node();
 
    //assign the data entered by user
    new_node->data = x;
 
    // node is inserted in beginning so, prev will always 
    // be NULL
    new_node->prev = NULL;
 
    //the node created is inserted at beginning so we need to
    //connect it with previous head
    new_node->next = (*head);
     
    // change the head to the current node’s address
    if ((*head) != NULL)
        (*head)->prev = new_node;
 
    (*head) = new_node;
}

void print_list(Node* node){
    while (node != NULL)
    {
        cout << node->data << ",";
        node = node->next;
    }
}

void pairSum(Node *head, int x){
    //initialize two pointers
    Node *left = head;
    Node *right = head;
    //move right pointer to last node
    while (right->next != NULL)
        right = right->next;
 
    // break the loop when two pointers meet
    // each other or cross each other
    while (left != right && right->next != left)
    {
        int sum = (left->data + right->data);
        // sum is equal to target so, pair found
        if (sum == x)
        {
            cout << "(" << left->data<< ", "
                << right->data << ")" << endl;
 
            // move left forward by one node
            left = left->next;
 
            // move right backward by one node
            right = right->prev;
        }
        else
        {
            if (sum < x)
                left = left->next;
            else
                right = right->prev;
        }
    }
}


int main()
{
    Node* head = NULL;
 
    add_at_begin(&head, 12);
    add_at_begin(&head, 10);
    add_at_begin(&head, 4);
    add_at_begin(&head, 3);
    add_at_begin(&head, 2);

    cout<<"The pairs with sum equal to target are: "<

						 

Output

The pairs with sum equal to target are:
(2, 12)
(4, 10)

Time Complexity: O(n), n is the total number of nodes in the list.
[forminator_quiz id=”5813″]

So, in this blog, we have tried to explain how we can find a pair with a given sum in a doubly-linked list in the most optimal way. 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.