Find pairs with given sum in doubly linked list

Easy
0/40
Average time to solve is 10m
92 upvotes
Asked in companies
OlaCentilytics | Intelligent Cloud Management

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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).

Sample input 1:

5
1 2 3 4 9
5


Sample output 1

2
1 4
2 3


Explanation for sample input 1 :

There are 2 pairs in the linked list having sum equal to 'k' (= 5).


Sample input 2:

5
1 10 11 12 27
7


Sample output 2:

0


Explanation for sample output 2

There is no pair in the linked list with sum equal to 'k' (= 7).


Expected time complexity :
The expected time complexity is O('n').


Constraints:
2 <= 'n' <= 10 ^ 4
1 <= 'data' in any node <= 10 ^ 4
1 <= 'k' <= 10 ^ 4

'data' in every node is distinct.

Time limit: 1 second
Hint

Think about finding the sum of all possible pairs.

Approaches (3)
Brute Force

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’.
Time Complexity

O(n ^ 2), where ‘n’ is the length of the doubly linked list.

We are using two nested loops. The outer loop is running ‘n’ times (compare it to a for loop having ‘i’ from 0 to ‘n’ - 1), and the inner loop is running ‘n’ - ‘i’ times.

So the total number of iterations:

= (‘n’ - 1) + (‘n’ - 2) + (‘n’ - 3) + … + 2 + 1

= (‘n’ - 1) * ‘n’ / 2

Hence the time complexity is O(n ^ 2).

Space Complexity

O(1)

We are using constant extra memory.

Hence the space complexity is O(1).

Code Solution
(100% EXP penalty)
Find pairs with given sum in doubly linked list
Full screen
Console