Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
1st Approach 
3.1.
Time Complexity: 
3.2.
Auxiliary Space Complexity 
4.
2nd Approach  
4.1.
C++ Implementation 
4.2.
Java Implementation 
4.2.1.
Output
4.3.
Time Complexity:
4.4.
Auxiliary Space Complexity 
5.
Frequently Asked Questions
5.1.
What's the difference between a linked list and an array?   
5.2.
Is it true that a linked list is a static data structure?  
5.3.
In a binary search tree, what is the difficulty of deletion? 
5.4.
In DSA, what is the AVL tree?  
5.5.
Is the linked list ordered? 
6.
Conclusion
Last Updated: Mar 27, 2024

Find a triplet from three Linked Lists with a sum equal to a given number

Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

This article will teach to solve a question where three separate linked lists and an integer will be provided as input. Now we need to see if there is a triplet (one from each list) that equals the specified integer.

Recommended Topic, Floyds Algorithm

Problem Statement

If we're given three linked lists: 3 ->8 ->1 ->5 ->NULL, 6 ->2 ->8 ->NULL, and 11 ->4 ->2 ->NULL, and the target = 14. Then, using the problem statement as a guide:

  • We must discover three Nodes (one from each list) that add up to 14 in total. 
     
  • If we take eight from the first list, two from the second list, and four from the third list, we will get the sum of target=14.
     
  • The triplet that is required will be (8,2,4).
     

We have grasped the problem statement at this point. Now we'll try to come up with a solution to this difficulty. 

Consider how you can address this challenge before continuing to the strategy section.

  • If you get stuck, don't worry; we'll go over how to solve the problem in detail in the next part.
     
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

1st Approach 

The first basic technique that springs to mind is to pick a node from the top of the list. Then we select a node from the second list for each node from the first list, and for each node from the second list selected, we select a node from the third list, and we verify whether the sum of the three nodes selected equals the target or not. We have our necessary triplet if the sum equals the aim. 

Time Complexity: 

O(N^3) Where N stands for the length of the Linked list. 

Reason: Here we are using three continuous nested loops so, the running time of this algorithm is cubic i.e O(N^ 3)

Auxiliary Space Complexity 

O(1) As the Linked list data structure is used.

Reason- Here we have used a pre-defined data structure from the collection. As a function of input attributes, the amount of memory space required to solve an instance of the computational problem is set to one.

Although the above method yields the proper outcome, it is time for Complexity. Is it possible to lower the time complexity? Let's see if we can do it with the following strategy.

2nd Approach  

  • To begin, we must sort the second and third lists (the second in ascending order and the third in descending order) to determine if moving forward or backward in the lists will raise or decrease the sum. 
     
  • Now we must fix a node in the first list and follow the instructions below for each node. 
     
  • Calculate the total of all three-pointers on each list in various positions. 
     
  • If the total exceeds the target, we must reduce the total, which requires us to proceed to the third list. 
     
  • Else If our total is less than the target, we must proceed to the second list to increase our total (as the second list is sorted in ascending order). 
     
  • If the sums are equal, we can easily print the triplet and demonstrate that one triplet was found in each of the three lists.

C++ Implementation 

#include<bits stdc++.h="">
using namespace std;
class Node{
     public:
    int val;
     Node* next;
    Node(int d){
         val = d;
        next = NULL;
    }
};


void sortSum(Node *start, Node *scnd,Node *third, int tgt)
{
    Node *aa = start;
 
    while (aa != NULL)
    {
        Node *bb = scnd;
        Node *cc = third;
 
   
        while (bb != NULL && cc != NULL)
        {
     
            int totalSum = aa->val + bb->val + cc->val;
            if (totalSum == tgt)
            {
            cout << "Triplet  detected: " << aa->val << " " <<bb->val << " " << cc->val;
            return;
            }
 
           
            else if (totalSum < tgt)
                bb = bb->next;
            else
                cc = cc->next;
        }
        aa = aa->next;
    }
 
    cout << "No triplet found";
    return;
}


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


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


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


   sortSum(start,scnd,third,14);  
}
</b-></bits>

 

Java Implementation 

class TripletClass
{
    Node head; 


    class Node{


        int val;


         Node next;


         Node (int d) {
              val = d; next = null ; 
                  }
    }
    boolean sortSum(TripletClass llista, TripletClass llistb, TripletClass llistc,int givenNumber)
    {
        Node a = llista.head;


        while (a != null)
        {
            Node b = llistb.head;


            Node c = llistc.head;


           
            while (b != null && c!=null)
            {
                int totalSum = a.val + b.val + c.val;
                if (totalSum == givenNumber)
                {
                    System.out.println("TripletClass found " + a.val +" " + b.val + " " + c.val);
                    return true;
                }
              
                else if (totalSum < givenNumber)
                    b = b.next;
                else
                    c = c.next;
            }
            a = a.next;
        }
        System.out.println("No TripletClass found");
        return false;
    }
    void push(int new_val)
    {
        Node new_node = new Node(new_val);
        new_node.next = head;
        head = new_node;
    }
    public static void main(String args[])
    {
        TripletClass llista = new TripletClass();
        TripletClass llistb = new TripletClass();
        TripletClass llistc = new TripletClass();


        llista.push(3);
        llista.push(8);
        llista.push(1);


        llistb.push(2);
        llistb.push(6);
        llistb.push(8);


        
        llistc.push(11);
        llistc.push(4);
        llistc.push(2);


        int givenNumber = 14;
        llista.sortSum(llista,llistb,llistc,givenNumber);
    }
}

Output

Triplet detected: 8 2 4

Time Complexity:

O(N ^ 2), Where ‘N’ stands for the length of the linked list.

Reason: As we are using a nested loop so the time complexity would be O(N) * O(N) ~ O(N^ N) 

Auxiliary Space Complexity 

O(1)

Reason- Here we have used a pre-defined data structure from the collection. As a function of input attributes, the amount of memory space required to solve an instance of the computational problem is set to one.

Frequently Asked Questions

What's the difference between a linked list and an array?   

An array is a group of elements with the same data type. A linked list is an ordered collection of elements of the same type, each of which is linked to the next via pointers. The array index can be used to access entries in an array at random. Linked lists do not allow for random access.

Is it true that a linked list is a static data structure?  

The primary distinction between arrays and linked lists is that arrays are static data structures, whereas linked lists are dynamic.

In a binary search tree, what is the difficulty of deletion? 

Time complexity is O in general (h). The deletion of element 1 necessitates a traversal of all elements to locate it (in orders 3, 2, 1). As a result, deletion in a binary tree has an O worst-case complexity (n). Time complexity is O in general (h).

In DSA, what is the AVL tree?  

A binary search tree in which the height difference between each node’s left and right subtrees is less than or equal to one is known as an AVL tree. Adelson, Velskii, and Landi discovered the approach for balancing the height of binary trees, which is known as the AVL tree or Balanced Binary Tree. 

Is the linked list ordered? 

Linked Lists, like stacks and queues, are a type of sequential collection. It doesn't have to be in any particular order. A linked list is a collection of independent nodes that can hold any type of data. Each node in the link has a reference to the next node.

Conclusion

This article has gone through Deleting Node in Different Situations, Removing an element from the list's beginning. The list is displayed in its entirety. Searches for an element using the specified key. Check out our articles in Library. You may also CheckOut our course on the linked list.

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Ninja, have a great time learning.

 

Previous article
Remove Duplicates from Linked List
Next article
Find the Sum of Last N Node of given Linked List
Live masterclass