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

Introduction

This blog will discuss an important problem of counting pairs from two linked lists whose sum is equal to a given value. Such problems do come in interviews.

Before solving the problem, it’s recommended that a known basic traversal in the Linked List check Linked List.

In this blog, we dive deep into each detail to get a number of pairs from two linked lists whose sum is equal to a given value.

Let’s look at the problem statement for this problem.

Problem Statement

We will be given a head pointer of two linked lists of size n and m of distinct elements and an integer target as input, and the problem is to count all pairs from both lists whose sum is equal to the given value target, i.e., Count pairs from two linked lists whose sum is equal to a given value target.

Example 1

Input-
List1 = 1->2->3->5->NULL
List2 = 2->4->5->10->12->NULL
Target= 7

Output: 3

Explanation:

Pairs : {(2,5) ,(3,4) ,(5,2)} These are 3 pairs whose sum is equal to target = 7.

Example 2

Input-
List1 = 1->3->5->8->NULL
List2 = 6->4->1->NULL
Target= 9

Output: 3

Explanation:

Pairs : {(3,6) ,(8,1) ,(5,4)} These are 3 pairs whose sum is equal to target = 9.

Approach 1

First, let’s look at the naive approach that would probably strike anybody’s mind before jumping to an optimal approach.

So, the basic approach is to select a node in the first linked list for each selected element. We iterate over every node in the second linked list and count the pair whose sum is equal to the target value.

Now let’s look at the PseudoCode.

PseudoCode

Algorithm

//Counts pairs from two linked lists whose sum is equal to a given //value
// pass list1,list2 and value target
countPairs(list1, list2, target)
  Intialize count = 0
  while list1 != NULL
      Data1 = list1_value
      while list2 != NULL
         Data2 = list2_value
         if Data1 + Data2 is equal to target
            Increase count by 1
         list2 = list2_next
      list1 = list1_next

Return count

CODE IN C++

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

// Linked list node
class Node{
public:
  int value;    //stores data of linked list
  Node *next;   //pointer for next node
  Node(int data){  //constructor to construct new node
      value=data;  // with given data 
      next=NULL;   
  }
};

/* function to count pairs from two linked lists whose sum is equal to given value */
int count_pairs(Node *head1, Node *head2, int target){
  int ans=0; //stores the count of pairs with given sum
  while(head1 != NULL){ // traverse the first linked list
     int data1 = head1->value;  //select a node in first linked list 
     Node *temp = head2;
     while(temp != NULL){   // traverse the second linked list
       int data2 = temp->value; 
       if(data1 + data2 == target) //check if pair has equal sum or not
       ans++;
       temp=temp->next; 
     }
     head1=head1->next;
  }
  return ans;
}
int main(){
// create first linked list with head pointer head1
  Node *head1 = new Node(1);
  head1->next = new Node(2);
  head1->next->next = new Node(3);
  head1->next->next->next = new Node(5);

// create second linked list with head pointer head2
  Node *head2 = new Node(2);
  head2->next = new Node(4);
  head2->next->next = new Node(5);
  head2->next->next->next = new Node(10);
  head2->next->next->next->next = new Node(12);

//store target 
  int target = 7;
  int ans = count_pairs(head1, head2, target);
  cout<<ans<<endl;
}

Input: 
head1 = 1->2->3->5
head2 = 2->4->5->10->12
target = 7
Output: 3

Time Complexity: O(n*m) where n = size of first linked list and m=size of second linked list.

This is because we iterate through two nested loops. Hence it’s O(n*m).

Space Complexity: O(1) at the worst case because no extra space is used.

The above algorithm works in O(n*m) time which is pretty slow. This gives us the motivation to improve our algorithm.

So let’s think about an efficient approach to solve the problem.

Approach 2

One of the good approaches to count pairs from two linked lists whose sum is equal to a given value is by using a hash table.

Now we can formulate our approach:

We store all elements of the first linked list in a HashSet.
Now iterate over the second linked list.
For each element, we have to check if (target - element) exists in the hash set or not and increase the answer accordingly.

Let’s look at the Code.

CODE IN C++

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

// Linked list node
class Node{
public:
  int value;    //stores data of linked list
  Node *next;   //pointer for next node
  Node(int data){  //constructor to construct new node
      value=data;  // with given data 
      next=NULL;   
  }
};

int count_pairs(Node *head1, Node *head2, int target){
   //declaring hashset for storing elements of first linked list
    unordered_set<int> hash_set;
    int ans =0;
    while(head1!=NULL){ // iterate over first list
      hash_set.insert(head1->value); //store the element in list in hash
      head1=head1->next;
    }
    while(head2!=NULL){
      int data = head2->value;
      if(hash_set.find(target-data)!=hash_set.end())
        ans++;
      head2=head2->next;
    }

   return ans;

}

int main(){
// create first linked list with head pointer head1
  Node *head1 = new Node(1);
  head1->next = new Node(2);
  head1->next->next = new Node(3);
  head1->next->next->next = new Node(5);

// create second linked list with head pointer head2
  Node *head2 = new Node(2);
  head2->next = new Node(4);
  head2->next->next = new Node(5);
  head2->next->next->next = new Node(10);
  head2->next->next->next->next = new Node(12);

//store target 
  int target = 7;
  int ans = count_pairs(head1, head2, target);
  cout<<ans<<endl;
}

Input: 
head1 = 1->2->3->5->NULL
head2 = 2->4->5->10->12->NULL
target = 7
Output: 3

Time Complexity: O(n + m) where n = size of first linked list and m=size of second linked list.

Since we traverse both lists once and access the hash table in O(1) time, the overall complexity is O(n + m).

Space complexity: O(n) as a form of storing the first list in a hash table.

Approach 3

There is another efficient approach with two pointers without any extra space. But It works on sorted linked lists. So first, we efficiently sort the list by using merge-sort in the list.

Note: You can practice Sort the LinkedList problem for better clarity regarding the sorting on the list.

Now we can formulate our approach:

We first sort first linked list in increasing order and the second linked list in descending order.
Take two pointers saying pointer1 and pointer2. Initially, pointer1 points to the starting node of the first linked list, and pointer2 points to the starting node of the second linked list.
Now iterate on both lists in the following ways:
1. If the pointer1-value + pointer2-value is greater than the target, it means we have to decrease the sum, so we have to move pointer2 by one node.
2. If pointer1-value + pointer2-value is less than the target, it means we have to increase sum, so we have to move pointer1 by one node.
3. If pointer1-value + pointer2-value is equal to target. Increase our count and move both pointer1 and pointer2 by one node.
Return our count if any pointer reaches its NULL.

Let’s look at the Code.

CODE IN C++

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

// Linked list node
class Node{
public:
  int value;    //stores data of linked list
  Node *next;   //pointer for next node
  Node(int data){  //constructor to construct new node
      value=data;  // with given data 
      next=NULL;   
  }
};

/* function to count pairs from two linked lists whose sum is equal to a given value */
int count_pairs(Node *head1, Node *head2, int target){
   //intialise both pointer with thier starting node.
    Node *pointer1 = head1;
    Node *pointer2 = head2;
    int ans = 0;
    while(pointer1 != NULL && pointer2 != NULL){
       int data1 = pointer1 -> value;
       int data2 = pointer2 -> value;
       if(data1 + data2 > target) 
          pointer2 = pointer2 -> next;
       
       else if(data1 + data2 < target)
          pointer1 = pointer1 -> next;

       else {
          ans++;
          pointer2 = pointer2 -> next;
          pointer1 = pointer1 -> next;
      }
    } 
   return ans;
}

int main(){
// create first linked list with head pointer head1
   Node *head1 = new Node(1);
   head1->next = new Node(2);
   head1->next->next = new Node(3);
   head1->next->next->next = new Node(5);

// create second linked list with head pointer head2
   Node *head2 = new Node(12);
   head2->next = new Node(10);
   head2->next->next = new Node(5);
   head2->next->next->next = new Node(4);
   head2->next->next->next->next = new Node(2);

//store target 
int target = 7;
int ans = count_pairs(head1, head2, target);
cout<<ans<<endl;
}

Input: 
head1 = 1->2->3->5->NULL
head2 = 12->10->5->4->2->NULL
target = 7
Output: 3

Time Complexity: O(nlogn + mlogm) where n = size of first linked list and m=size of second linked list.

We sort both list in O(nlogn + mlogm) +traverse the both list in worst case O(n + m), so overall complexity is O(nlogn + mlogm).

Space complexity: O(1) at the worst case because no extra space is used.

Frequently Asked Questions

What are the advantages of Linked List?

Some advantages of the linked list are as follows:

Insertion and deletion operations can be implemented very easily, and these are not costly as they do not require the shifting of elements.
They are dynamic. Hence, we can change their size whenever required.
Stacks and queues can be implemented very easily using Linked Lists.

How does merge sort for linked list work?

The merge sort algorithm is a divide and conquers algorithm it divides the list into smaller sublists until each sublist contains only a single element, and a list of size one is always sorted; using this property, it merges two sorted sublists into a single sorted list.

Can we use two pointer approach without sorting the lists?

No, Because in the unsorted list we can’t decide whether its next element is greater or less than the current element. So we don’t move our pointer to increase or decrease the sum.

Conclusion

This article taught us how to solve the problem of data structure, i.e., count pairs from two linked lists whose sum is equal to a given value. We also saw how to approach the problem using a naive approach followed by two efficient solutions. We discussed an iterative implementation and some basic traversal in linked lists using examples, pseudocode, and code in detail.

We hope you understand how we can apply two pointer approach or use of hash set in such problems.

Now, we recommend you to solve some problems based on the concepts of this problem—another similar problem is the Number of pairs with a given sum.

More suggested problems based on LinkedList are Remove Duplicates from Sorted List, Add One to LinkedList, Cycle Detection in Singly LinkedList, and many more.

I hope that this blog has helped you enhance your knowledge regarding the above Data Structures and Algorithms problem and if you would like to learn more, check out our articles on the CodeStudio. Enroll in our courses, refer to the test series and problems available and look at the interview bundle for placement preparations.