Find pair for given sum in a sorted singly linked without extra space

Introduction

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

Problem Statement

In this problem, we are given a sorted singly linked list and a value k, our task is to find the pairs whose sum is equal to K.

Note: we can consider a node in one pair only.

Example:

Input : head → 0 → 2 → 3 → 7 → 8 → 10 , K = 10.

Output:
0 10
2 8
7 3

Problem Statement Understanding

Let’s first understand the problem statement with the help of examples.
Let’s say we are given the sorted linked list : head -> 1 -> 1 -> 2 -> 4 -> 6 -> 7 -> NULL and K = 8.

  • Then here, we will make a pair of the first 1 with 7.
  • After that we cannot make a pair of the 2nd 1 with 7 because this 7 has been already used in one of the pairs.
  • Now we have a pair of 2 and 6.
  • So our answer pairs would be (1,7) and (2,6).

Let’s move to the next section to see this process in more depth.

Approach 1

The naive way to do this problem is to traverse over each element one by one and search for the second element in the remaining linked list in a forwarding direction whose sum with the first value is equal to the given value K.

Algorithm

  • Take two-pointer ptr1 and ptr2 pointing to head initially.
  • Take ptr1→data as the first value and search for the K - (ptr1→data) as the second value in the remaining linked lists in the forwarding direction.
  • We find the K-(ptr1->data) using a pointer ptr2. So if there exists a ptr2 such that ptr1->data + ptr2->data == k then we print ptr1->data and ptr2->data and delete node pointed by ptr2 as we mentioned in the problem statement that one node should be considered in only one pair.
  • So if we don’t delete ptr2 then it may be counted again for some other duplicate ptr1->data.
  • Like in the example linked list head -> 1 -> 1 -> 2 -> 4 -> 6 -> 7 -> NULL and k = 8 here 7 can be considered in for both 1’s if we don’t delete it after considering it once.
  • Now, increment ptr1 = ptr1→next and assign ptr1 to ptr2 because in search of the second element the ptr2 reaches the end of the linked list.
  • Do the same work for every element till ptr1→data <= K/2, because if we are traversing for nodes that have ptr1→data greater than K/2 then we have to search for value K - (ptr1→data) that is smaller than ptr1→data, and it is impossible to find that value in remaining linked list which is sorted.

Time Complexity: O(N2), because for every element, we are searching for its pair.
Space Complexity: O(1), No extra space is used.

Dry Run for approach 1

For better understanding follow dry run along with code

Approach 2

We can apply some optimization to our previous approach by using hashtable/map.

Algorithm

  • We will insert every value of the sorted linked list as a key in the hashtable/map. And keep the count of occurrences of every distinct value.
  • Take a pointer ptr1 initially pointing to the head.
  • We will start traversing over every element of the linked list till ptr1→datadata) is present in the hashtable and its frequency is more than one then print ptr1->data and (K - ptr1->data).
  • And decrement the occurrence of (K - ptr1->data) to ensure that the same element is not counted in more than one pair.
  • And if ptr->data == (k-ptr->data) then the frequency of ptr->data should be more than 1 to be considered as a valid pair. And we will print ptr->data and (k-ptr->data) (ptr->data)/2 times.

Time Complexity: O(N), because for every element, we are searching for its pair and searching in the hashtable is O(1).
Space Complexity: O(N) because we are keeping a hashtable.

Dry Run for approach 2

For better understanding follow dry run along with code

Finally, we have optimized our solution and now our time complexity is O(N) but we are using extra space which is against the problem statement because we have to find all the pairs whose sum is equal to K without using extra space.

Approach 3

The efficient solution to this problem is to use an XOR linked list.
In a singly linked list, we can traverse the list only in the forward direction. But if we use XOR concept to convert a singly linked list to doubly linked list then we can travel in the singly-linked in both directions.
Now we will use the concept of two pointers because we can move in both directions by exploiting the property of XOR.
So the main idea here is that since the linked list is sorted, we will keep a pointer ptr1 at the beginning of the list and another pointer ptr2 at the end of the list.
And now if ptr1->data + ptr2->data data+ptr2->data hence we will move ptr1=ptr1->next.
If
ptr1->data + ptr2->data > k then it means that we have to decrease the sum ptr1->data + ptr2->data hence we will move ptr2 one step backward analogous to ptr2--.
And if
ptr1->data + ptr2->data == K__ then we have found one required pair so print them and move ptr1 to point to the next node and ptr2 to point to one previous node.

Algorithm

  • We know that in the singly linked list we have only the address of the next node not of the previous node, so we have to convert our singly linked list into a doubly linked list.
  • The doubly linked list we are talking about here is XOR linked list, which is also known as memory efficient doubly linked list.
  • The next pointer of each node in the XOR linked list contains the XOR of the previous node’s address and the next node’s address.
  • After converting singly linked list into XOR linked list we will initialize two pointers ptr1 and ptr2 variables the ptr1 will be assigned with the head and the ptr2 will be assigned with the last node’s address.
  • If ptr1→data + ptr2→data == K then print both ptr1→data and ptr2→data,but if ptr1→data + ptr2→data > K then we move ptr2 in backward direction by find out the address of the previous node using xor’s property and if ptr1→data + ptr2→data < K then we move ptr1 in forward direction.
  • The above action will execute till ptr1 == ptr2.

Dry Run for approach 3

For better understanding follow dry run along with code

Code Implementation

// find XOR of previous and next node address
struct Node* XOR (struct Node *a, struct Node *b){ 
    return (struct Node*) ((uintptr_t) (a) ^ (uintptr_t) (b)); 
} 


// convert singly linked list to XOR linked list
void convertSinglyToXORlist(struct Node *head){
    struct Node *next_node; 
    struct Node *prv = NULL;  
    while (head != NULL){  
        next_node = head->next;  //next node 
        head->next = XOR(next_node, prv);// finding XOR of prv and next Node 
        prv = head; 
        head = next_node; 
    } 
} 

void pairSumToK(struct Node *head, int K){

    //both first and second pointer initialized with head
    struct Node *first = head; 
    struct Node *second = head; 

    struct Node *next_node = NULL, *prv_node = NULL; 

    while (second->next != prv_node){ 
        struct Node *temp = second; 
        second = XOR(second->next, prv_node); 
        prv_node = temp; 
    } 
 
    next_node = NULL; 
    prv_node = NULL; 

    while (first != NULL && second != NULL && first != second && first != next_node){ 
        if ((first->data + second->data)==K){
            // sum of first Node and second Node's data is equal to K
            // then print its value  
            cout<data<<" "<data<next,prv_node); 
            prv_node = temp; 

            temp = second; 
            second = XOR(second->next, next_node); 
            next_node = temp; 
        } 
        else
        { 
            if ((first->data + second->data) < K){ 
            // if sum of first and second node's data is smaller than k
            // move first pointer forward
                struct Node *temp = first; 
                first = XOR(first->next,prv_node); 
                prv_node = temp; 
            } 
            else{
            // if sum of first and second node's data is greater than k
            // move second pointer backward
                struct Node *temp = second; 
                second = XOR(second->next, next_node); 
                next_node = temp; 
            }
        } 
    } 
} 


Output

(1,7)
(2,6)

Time Complexity: O(N), because we have traversed through every node of the linked list.

So, in this blog, we have learned to Find pairs for a given sum in a sorted singly linked list without extra space, and in this process, we also learn how to build intuition regarding any problem and how to optimize the solution. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Clone a linked list with next and random pointer in O(1) space
Next post Sort a Linked List of 0s, 1s and 2s

Leave a Reply

Your email address will not be published. Required fields are marked *