Find a triplet from three linked lists with a sum equal to a given number

Problem Statement

We will be given three different linked lists and an integer as input. Now, we need to find whether there is a triplet (one from each list) that sums up to the given integer.

Problem Statement Understanding

To understand the problem statement, let us take examples.

If the linked lists given to us are 3→8→1→5→NULL, 6→2→8→NULL, and 11→4→2→NULL, and the target = 14. Then, according to the problem statement:

  • We need to find three Nodes (one from each list) such that they sum up to 14.
  • If we select 8 from the first list, 2 from the second list and 4 from the third list, we will get the sum equal to the target=14.
  • The required triplet will be (8,2,4).

At this point, we have understood the problem statement. Now we will try to formulate an approach for this problem.

Before moving to the approach section, try to think about how you can approach this problem.

  • If stuck, no problem, we will thoroughly see how we can approach this problem in the next section.

Let’s move to the approach section.

Approach 1

The naive approach that comes to our mind is to first select a node from the first list. Then for each node of the first list, we select a node from the second list, and for each selected node of the second list, we select a node in the third list, and then we check if the sum of the 3 nodes selected is equal to target or not. If the sum is equal to the target, we have our required triplet.

Time Complexity: O(n^{3}), n is the number of nodes in a list.

The above approach gives the correct result, but its time complexity is high. Can we reduce the time complexity? Let us find out If we can do so in the below approach.

Approach 2

  • First, we need to sort the second and third lists (the second list will be sorted in ascending order and the third list in descending order), so that we could be sure whether moving forward or backward in the lists is going to increase or decrease the sum.
  • Now, we need to fix a node in the first list and for each node, we need to perform the below steps.
  • Calculate the sum of all three-pointers present at different positions on each list.
  • If the sum is greater than the target, then we need to decrease the sum, so we need to move forward in the third list (if you visualize carefully, you can see that moving forward in the third list will decrease the sum, because the third list is sorted in descending order).
  • Else If the sum is smaller than the target, we need to move forward in the second list to increase our sum (as the second list is sorted in ascending order).
  • If the sum is equal, then we can easily print the triplet and show that we have found one triplet in the three given lists.

To see the above approach in more detail, move to the algorithm section.

Algorithm

1) First, sort the second list in ascending order and the third list in descending order.
2) Initialize a pointer a with head of first list.
3) Run a while loop till a is not NULL and inside the loop:

  • Initialize pointer b and c with head of second and third list, respectively.
  • Run a while loop till b and c are not NULL.
    • Initialize variable sum as the sum of values pointed by pointers a,b, and c.
    • If the sum is equal to the target, print the values pointed by a,b, and c and return from the function.
    • If the sum is less than the target, move forward b by one node. Else, move forward c by one node.
  • Move forward a by one node.

Note: For simplicity, in dry run and code implementation, we took second and third linked lists, which are already sorted in ascending and descending order, respectively. If you want to know how to sort a linked list, please feel free to refer to this article for sorting related concepts of linked list. Also, inside the code implementation, we haven't provided the sorting function (function to sort the linked list); if you want to take unsorted linked lists, please sort them in proper format (the second list will be sorted in ascending order and the third list in descending order) using code from above-mentioned article, before passing them to isSumSorted() function in the code.

Dry Run





Code Implementation

#include
using namespace std;
class Node{
    public:
    int data;
    Node* next;
    Node(int x){
        data = x;
        next = NULL;
    }
};

void isSumSorted(Node *first, Node *second,Node *third, int target)
{
    Node *a = first;
 
    //Select a node in first list and
    //traverse the other two lists for
    //each selected node
    while (a != NULL)
    {
        Node *b = second;
        Node *c = third;
 
        //select posssible pairs of nodes
        //from second and thirs list
        //(one from each list)
        while (b != NULL && c != NULL)
        {
            // if sum is equal to our target
            int sum = a->data + b->data + c->data;
            if (sum == target)
            {
            cout << "Triplet Found: " << a->data << " " <data << " " << c->data;
            return;
            }
 
            // If sum is less than target
            else if (sum < target)
                b = b->next;
            else
                c = c->next;
        }
        a = a->next; // Move ahead in list a
    }
 
    cout << "No such triplet";
    return;
}

int main(void){
    Node* first = NULL;
    first = new Node(3);
    first->next = new Node(8);
    first->next->next = new Node(1);

    Node* second = NULL;
    second = new Node(2);
    second->next = new Node(6);
    second->next->next = new Node(8);

    Node* third = NULL;
    third = new Node(11);
    third->next = new Node(4);
    third->next->next = new Node(2);

    isSumSorted(first,second,third,14);  
}

Output

Triplet Found: 8 2 4

Time Complexity: O(n^2) ,n is the number of nodes in the list.

So, in this blog, we have tried to explain how you can Find a triplet from three linked lists with a sum equal to a given number most optimally. 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 Make loop at K-Th position in the Linked List
Next post Merge Two Unsorted Linked Lists To Get A Sorted List

Leave a Reply

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