Problem

Submissions

Hints & solutions

Discuss

Find Pairs

Easy

0/40

Average time to solve is 18m

Contributed by

6 upvotes

Asked in companies

Problem statement

We are given a sorted doubly-linked list which contains distinct positive integers, and an integer ‘X’. Print all such unique pairs from the given list so that their sum is equal to ‘X’.

Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line of the input contains the elements of the doubly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

The second line contains a single integer ‘X’.

Output format :

Print pair elements separated by a single pace where the first element of the pair should be less than the second element of the pair. The order of pairs does not matter.

Print each unique pair in a separate line.

Note :

You do not need to print anything, it has already been taken care of. Just implement the function and return the answer.

Follow Up:

Try to solve this problem in linear time complexity without using any other data structures.

Constraints :

1 <= N <= 5*10^5
-2*10^9 <= X <= 2*10^9
-10^9 <= data <= 10^9 and data != -1

Where ‘N’ is the length of the linked list and ‘X’ is the required pair sum value.

Time Limit: 1 sec

Sample Input 1:

2 7 10 14 15 19 22 27 -1
29

Sample Output 1:

Explanation For Sample Input 1:

There are four such pairs possible (2, 27), (7, 22), (10, 19), (14, 15) whose sum is 29.

Sample Input 2:

1 4 7 9 11 21 23 29 31 37 41 43 45 48 -1
52

Sample Output 2:

Explanation For Sample Input 2:

There are six such pairs possible (3, 48), (7, 45), (9, 43), (11, 41), (21, 31), (23, 29) whose sum is 52.

Hint 1

Hint 2

Hint 3

Try to explore all the possible pairs.

Approaches (3)

Approach 1

Approach 2

Approach 3

Brute Force Approach

A simple approach for this problem is to explore all the pairs and print those pairs which have the sum equal to ‘X’.

Pick one by one each node and pivot that node.
Find all nodes in the remaining list by traversing in the forward direction such that whose sum with the pivoted node is equal to the ‘X’.

Time Complexity

O(N^2), where ‘N’ is the number of nodes in the doubly linked list.

For each pivoted node, we are exploring all other nodes thus there are total N*(N+1)/2 nodes. So Overall Time complexity is O(N^2)

Space Complexity

O(1)

we are not using any extra space here.

(100% EXP penalty)

Find Pairs

Console