# Find Pair With A Given Sum In A Sorted Doubly Linked List

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

## Problem Statement:

Given a sorted doubly linked list of positive distinct elements, the task is to find pairs in a doubly-linked list whose sum is equal to the given value **num.**

## Discussed Solution Approaches:

- The brute force approach using
**nested loops** - Time optimized approach using
**Hashing** - Space and Time optimized approach using
**the two-pointer**method

## The key takeaway from this coding problem:

- Learn about
**Hashing** - Learn about the
**two-pointer**approach

For example:Suppose we have a sorted doubly-linked list as

5 <-> 7 <-> 10 <-> 15 <-> 20and we are given the value ofnumis 17 i.e.num = 17.Now we have to find two integers from the sorted doubly-linked list which gives the total sum as17.So, we can clearly see that integers7 and 10together add up to17,hence, in this case, the two numbers will be7 and 10

**Can you do it in the time complexity of O(n) with the space complexity of O(1)?**

Now, for time being forget the time complexity you have been given to find out the solution, for now, think of the most basic way to find a solution to the problem.

## Naive Solution:

The **brute-force **solution of the above problem would be using a nested loop to take a single integer and find the other integers whose sum is equal to the given **num.**

Let’s look at the approach of this method:

`- Pick the first integer from the doubly-linked list`

- Calculate the difference between the given num and the current integer in the doubly-linked list and store it in a variable **diff**

- Now, search for **diff** by traversing the complete linked list which will be the second number in the list (if present)

**The time complexity for this problem will be O(n²), n is the total number of nodes in the doubly linked list.**

Now, since this was a brute force solution, if you think a bit closely on optimization of the time complexity we can have a bit optimized solution.

Can you think of any such solution?

If you are not able to think let me give you a bit of a hint, we can solve the above problem with the help of **hashing **in **O(n) time.**

## Hashing Solution:

Let us have a glance at this hashing algorithm.

start function findPair(reference to the headNode, number) unordered_set<int> nodeHash;

struct node *headRef = headNode;

start while(headRef->next is not NULL)

insert headRef->data to nodeHash

end while bool nodeFound = false; start while(headRef->next is not NULL)

int diff = number - headRef->data

start if(diff is present in nodeHash)

print(diff and headRef->data)

set nodeFound to true

break the loop

end if

end while start if(nodeFound is false)

print("Not Found")

end ifend findPair

Now, analyzing the above approach we see that this algorithm has a **time complexity of O(n)** which is quite good enough to solve this problem, but looking into the space complexity of the algorithm we see that it takes an **O(n) space** which is not an optimized solution in terms of space complexity.

Can we do it even better?

Think of an approach where we can do this problem in **O(n) time and O(1) space.**

Yes, we can do it in constant space by making use of the two-pointer approach and simply traversing and finding the pair if it exists.

Let us see this efficient approach.

## Two-Pointer Solution:

Let us have a glance at this most efficient algorithm in terms of space and time.

start function findPair(reference to the headNode, number)

struct node *headPointer = headNode

struct node *tailPointer = headNode start while(tailPointer->next is not NULL)

tailPointer = tailPointer->next

end while bool foundNode = false start while(headPointer is not equal to tailPointer and tailPointer->next is not equal to headPointer)

start if(headPointer->data + tailPointer->data == number)

print(headPointer->data and tailPointer->data)

set foundNode as true

break the loop

end if

start else

start if(headPointer->data + tailPointer->data < number)

headPointer = headPointer->next

end if

start else

tailPointer = tailPointer->prev

end else

end else

end while start if(foundNode is false)

print("Not Found")

end ifend findPair

Now, since you already know the algorithm behind the problem so, you can write your own functional **code **in your desired programming language.

## Analyze:

- Time Complexity:
`O(n)`

, where**n**is the size of the given doubly-linked list this is because we are traversing the list only once. - Space Complexity:
`O(1)`

, since we are not using any extra space to store the integers or the nodes.

**Keep learning and keep growing and also keep exploring more!**

**All the very best!**

For more interesting and informative articles and tips follow me on **Medium**** and ****Linkedin**