Count pairs from two linked lists whose sum is equal to a given value

Problem Statement

We will be given two linked lists and an integer target as input, and we need to count pairs of integers in both lists such that each element of the pair belongs to different lists and their sum is equal to the given target integer.

Problem Statement Understanding

To understand the problem statement, let’s take an example.

If the linked lists given to us are 1→3→5→8→NULL, 6→4→1→NULL, and the target = 9. Then, according to the problem statement:

  • We need to find pairs of integers such that each element of the pair belongs to a different list, and their sum is equal to 9.
  • All such pairs are - (3,6), (8,1) and (5,4)
  • There are three possible pairs, so; we need to print 3 as output, i.e., the total count of possible pairs.

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

Before moving to the approach section, try to think about how you can approach this problem.

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

Let’s move to the approach section.

Approach 1

The naive approach that comes to our mind is that first, select a node in the first list and for each selected node in the first list, iterate in the second list and check if the sum of node’s (selected node from first list + node from the second list) is equal to the target or not.

Time Complexity: O(N2), N is the number of nodes in a list.
Space Complexity: O(1)

The above approach gives the correct result, but its time complexity is high. Can we reduce the time complexity? Let us find out If we can do so in the below approach.

Approach 2

  • In this approach, we store all elements of the first list in a HashSet.
  • Then, we iterate on the elements of the second list and find if the difference in the value of the current element of the second list and target exists in hash or not.
  • If it exists in the HashSet, then we will increase the count by one.

Algorithm

1) Initialize a result variable with 0 and create an unordered set.
2) Push all elements of the first list in the set created above.
3) Run a while loop till head2 (pointer to the second list) is not NULL.

  • Check if (target - head2->data) exists in the set or not
    • If it exists then, increment the result by one.
  • Move the pointer head2 forward by one node.
    4) After the loop is executed, return result from the function.

Code Implementation

#include
using namespace std;
class Node{
    public:
    int data;
    Node* next;
    Node(int x){
        data = x;
        next = NULL;
    }
};

int countPairs(Node* head1, Node* head2,int target)
{
    int result = 0;
     
    unordered_set hash_set;
     
    //insert all elements of first list in
    //the hash set 
    while (head1 != NULL)
    {
        hash_set.insert(head1->data);      
        head1 = head1->next;
    }
     
    // iterate on each elements of second list
    while (head2 != NULL)   
    {
        //find if (target - currentData) exists
        //in the hashset
        if (hash_set.find(target - head2->data) != hash_set.end())
            result++;
         
        head2 = head2->next;   
    }
    // return the result    
    return result;
}
int main(void){
    Node* first = NULL;
    first = new Node(1);
    first->next = new Node(3);
    first->next->next = new Node(5);
    first->next->next->next = new Node(8);

    Node* second = NULL;
    second = new Node(6);
    second->next = new Node(4);
    second->next->next = new Node(1);
    cout<<"Count of pairs having sum "<<9<<" are: ";
    cout<

						 

Output

Count of pairs having sum 9 are: 3

Time Complexity: O(n), n is the number of nodes in a list.
Space Complexity: O(n), n is the number of nodes in a list.

In the above approach, we are using extra space to store the elements in a hash set. Can we reduce the extra space used? Let us find out If we can do so in the below approach.

Approach 3

  • At first, we need to sort the first list in ascending order and the second list in descending order.
  • The above step is performed so that we can predict whether moving forward in the lists is going to increase our current sum or decrease it.
  • It is evident that moving forward in the first list is going to increase the pair sum, and moving forward in the second one is going to decrease it.
  • Now, we will initialize two different pointers at the head of both lists.
  • We will compute the sum pointed by the pointers in each step, and If the sum is equal to the target, we will increase our result by one and move both pointers simultaneously.
  • If the sum is less than the target, we need to increase it so we will move the pointer of the first list forward by one node.
  • Else, we will move the pointer of the second list by one node.

Algorithm

1) Sort the first list in ascending order and the second list in descending order.
2) Initialize a variable result by 0.
3) Run a while loop till any one of first or second becomes NULL.
4) Calculate sum as the sum of data of nodes pointed by first and second pointers.
5) If the sum is equal to the target, increase the result by one and move both pointers forward by one node.
6) If the sum is greater than the target, move the second pointer forward by one node.
7) Else, move the first pointer forward by one node.

Note: For simplicity, in dry run and code implementation, we took the first and the second linked lists, which are already sorted in ascending and descending order, respectively. If you want to know how to sort a linked list, please feel free to refer to this article for sorting related concepts of linked list. Also, inside the code implementation, we haven't provided the sorting function (function to sort the linked list); if you want to take unsorted linked lists, please sort them in proper format (the first list will be sorted in ascending order and the second list in descending order) using code from the above-mentioned article, before passing them to countPairs() function in the code.

Also, note that to sort a linked list in descending order, you can first sort the linked list in ascending order, and then you can reverse the sorted linked list.

Dry Run


Code Implementation

#include
using namespace std;
class Node{
    public:
    int data;
    Node* next;
    Node(int x){
        data = x;
        next = NULL;
    }
};

int countPairs(Node* first, Node* second,int target)
{
    int result = 0;
    
    // iterate both lists
    while (first != NULL && second != NULL)
    {
        //calculate 'sum' 
        int sum = first->data + second->data;

        //if sum equals target, increase result by 1
        //and move both pointers
        if (sum == target)
        {
            first = first->next;
            second = second->next;
            result++;    
        }    
        
        // if sum is more than target, move 
        // second pointer
        else if (sum > target)
            second = second->next;
            
        // else move first pointer    
        else
            first = first->next;
    }        
        
    // required count of pairs     
    return result;
}

int main(void){
    Node* first = NULL;
    first = new Node(1);
    first->next = new Node(3);
    first->next->next = new Node(5);
    first->next->next->next = new Node(8);

    Node* second = NULL;
    second = new Node(6);
    second->next = new Node(4);
    second->next->next = new Node(1);
    cout<<"Count of pairs having sum "<<9<<" are: ";
    cout<

						 

Output

Count of pairs having sum 9 are: 3

Time Complexity: O(N log N), N is the number of nodes in the list
Space Complexity: O(1)

So, in this blog, we have tried to explain how to count pairs from two linked lists whose sum is equal to a given value, most optimally. 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 Merge Two Unsorted Linked Lists To Get A Sorted List
Next post Menu Driven Program For All Operations On Doubly Linked List in C

Leave a Reply

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