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

Published in

Javarevisited

4 min readSep 12, 2021

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

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