# 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 as5 <-> 7 <-> 10 <-> 15 <-> 20and 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;    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`

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

--

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