Javarevisited
Published in

Javarevisited

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

Doubly-Linked List

Problem Statement:

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
Let’s look at the code :p

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;

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 if
end findPair

Two-Pointer Solution:

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

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Swapnil Kant

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