Published in

Javarevisited

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

## 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:

For example:Suppose we have a sorted doubly-linked list as
5 <-> 7 <-> 10 <-> 15 <-> 20
and we are given the value of num is 17 i.e. num = 17. Now we have to find two integers from the sorted doubly-linked list which gives the total sum as 17.So, we can clearly see that integers 7 and 10 together add up to 17, hence, in this case, the two numbers will be 7 and 10

## Naive Solution:

- 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)

## Hashing Solution:

start function findPair(reference to the headNode, number)  unordered_set<int> 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)
set nodeFound to true
break the loop
end if
end while
start if(nodeFound is false)
end if
end findPair

## Two-Pointer Solution:

start function findPair(reference to the headNode, number)
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)
set foundNode as true
break the loop
end if
start else
start if(headPointer->data + tailPointer->data < number)
end if
start else
tailPointer = tailPointer->prev
end else
end else
end while
start if(foundNode is false)
end if
end findPair

## 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.

--

--

## Get the Medium app

Hi, I am Swapnil Kant, an avid programmer, and a full-time learner! One who is highly interested in Algorithm Optimization and Development