Last Updated: 9 Feb, 2021
Find pairs with given sum in doubly linked list
Easy
Asked in companies
A doubly-linked list is a data structure that consists of sequentially linked nodes, and the nodes have reference to both the previous and the next nodes in the sequence of nodes.
You are given a sorted doubly linked list of size 'n', consisting of distinct positive integers, and a number 'k'.
Find out all the pairs in the doubly linked list with sum equal to 'k'.
Example :
Input: Linked List: 1 <-> 2 <-> 3 <-> 4 <-> 9 and 'k' = 5
Output: (1, 4) and (2, 3)
Explanation: There are 2 pairs in the linked list having sum 'k' = 5.
Input Format:
The first line contains a single integer 'n', the number of elements in the doubly linked list.
The second line contains 'n' integers, the elements of the doubly linked list.
The third line contains a single integer 'k', the sum the pairs should have.
Output format:
The first line contains a single integer 'count', denoting the number of pairs having sum 'k'.
The next 'count' lines contains two integers each, the pair having sum 'k'. Each line will have one pair.
Note
You don’t have to print anything, it has already been taken care of. Just return the list of the valid pairs in any order.
In the output, the first term in each pair will be smaller than the second term, and the pairs will be printed in sorted order (according to the first term).
Approaches
We will find all the possible pairs by iterating over the whole doubly linked list ‘n’ times, where ‘n’ is the length of the linked list. At any time if the sum of any pair is equal to ‘k’, we will add it to our answer.
The steps are as follows:
findPairs(Node * ‘head’, int ‘k’)
- Let ‘ans’ be the list of the valid pairs.
- Initialize a pointer ‘ptr1’ = ‘head’, and it will be used to iterate over the linked list.
- Iterate while ‘ptr1’ is not NULL :
- Initialize a pointer ‘ptr2’ = ‘ptr1→next’.
- Iterate while ‘ptr2’ is not NULL:
- If the sum of ‘ptr1→data’ and ‘ptr2→data’ is equal to ‘k’ then add a pair of ‘ptr1→data’ and ‘ptr2→data’ into ‘ans’.
- ‘ptr2’ = ‘ptr2→next’
- ‘ptr1’ = ‘ptr1→next’
- Return ‘ans’.
We will scan the doubly linked list from left to right and we will use the Hash to store all previously encountered elements. So at each step, we will check if ‘k’ - (current node data) already exists in Hash, if yes we can say we have found a pair.
The steps are as follows:
findPairs(Node * ‘head’, int ‘k’)
- Let ‘ans’ be the list of the valid pairs.
- Initialize a pointer ‘ptr1’ = ‘head’, it will be used to iterate over the linked list.
- We are using a Hash Set (unordered_set) named ‘hash’.
- Iterate while ‘ptr1’ is not NULL :
- Let ‘val’ = ‘ptr1→data’
- If (‘k’ - ‘val’) exists in ‘hash’ then add a pair of ‘val’ and (‘k’ - ‘val’) into ‘ans’, otherwise insert ‘val’ into ‘hash’.
- ‘ptr1’ = ‘ptr1→next’
- Return ‘ans’.
As the given linked list is sorted so we can use two pointer technique to find the pairs in O(n) time complexity.
We will use two pointer variables ‘start’ and ‘end’ to find the candidate elements in the sorted doubly linked list.
Please note that the loop condition ‘start’ != ‘end’ is not enough, because the pointers might cross each other. It is simpler to compare their data.
The steps are as follows:
findPairs(Node * ‘head’, int ‘k’)
- Let ‘ans’ be the list of the valid pairs.
- Let ‘start’ and ‘end’ be two pointers, both initialized to ‘head’. Iterate ‘end’ to the last node of the linked list.
- While ‘start→data’ < ‘end→data’ :
- If the sum of data at ‘start’ and ‘end’ is equal to ‘k’, add the pair of ‘start→data’ and ‘end→data’ to ‘ans’ and update ‘start’ and ‘end’ to their next and previous nodes respectively.
- If the sum is less than ‘k’, then we move ‘start’ in the forward direction.
- If the sum is greater than ‘k’, then we move ‘end’ in the backward direction.
- Return ‘ans’.