Find triplet sum closest to X in a sorted Doubly Linked List (DLL)
Given a sorted doubly linked list of N nodes and an integer X, the task is to find the sum of three nodes in the list which is closest to X.
Examples:
Input: DLL: -8 ? 2 ? 3 ? 4 ? 5, X = 1
Output: 1
Explanation: The required three integers {-8, 4, 5} whose sum is 1 and is closest to 1.Input: DLL: 1 ? 2 ? 3 ? 4, X = 3
Output: 6
Explanation: The required three integers are {1, 2, 3} whose sum is 6 and is closest to X = 3.
Naive Approach: The simplest approach to solve the given problem is to generate all possible triplets using three nested loops and then choose the triplet which has the sum closest to X and print the sum of the triplet.
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: To optimize the above approach, the idea is to use 3 pointer technique. Follow the steps below to solve this problem:
- Initialize 4 variables, first and second pointing to the head node of the doubly linked list, i.e., first = head, second = head, and tail and third both initialized to the last node of the doubly linked list.
- Initialize a variable diff, initialized as INT_MAX, which stores the closest sum to X.
- Iterate while the first node is not NULL and perform the following steps:
- Initialize second to the next of first, i.e., second = first?next and third = tail(the last node of doubly linked list).
- Iterate while second and third are not NULL and third is not equal to the second.
- Initialize a variable say, sum as (first?data + second?data + third?data).
- If the absolute value of X – sum is less than the absolute value of X – diff, then update the value of diff as sum.
- If sum is less than X, then increment second pointer, i.e., second = second?next.
- Otherwise, decrement third, i.e., third = third?prev.
- Move the first pointer to the next pointer, i.e., first = first?next.
- After completing the above steps, print the value of diff as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Doubly linked list node struct Node { int data; struct Node *next, *prev; }; // Function to insert a new node at // the beginning of doubly linked // list void insert( struct Node** head, int data) { // Allocate node struct Node* temp = new Node(); // Fill the data value in it temp->data = data; temp->next = temp->prev = NULL; // If head is NULL change // head to temp if ((*head) == NULL) { (*head) = temp; } // Insert the node before head else { temp->next = *head; (*head)->prev = temp; (*head) = temp; } } // Function to find sum of triplet // closest to X void closestTripletSum( struct Node* head, int X) { // Points to the first node // of the triplet struct Node* first = head; // Points to the second node // of the triplet struct Node* second = head->next; // Stores the last node of // doubly linked list struct Node* tail = head; // Traverse till end of the list while (tail->next != NULL) { tail = tail->next; } // Stores the sum closest to X int diff = INT_MAX; // Points to the third node // of the triplet struct Node* third = tail; // Iterate till the end of the list while (first != NULL) { second = first->next; third = tail; while (second != NULL && third != NULL && third != second) { int sum = (first->data + second->data + third->data); // Check if the current sum // is closest to X if ( abs (X - sum) < abs (X - diff)) { // Update the value of diff diff = sum; } // Check if sum is less than X if (sum < X) { // Increment the second // pointer second = second->next; } else { // Decrement the third // pointer third = third->prev; } } // Move the first pointer // ahead first = first->next; } // Print the closest sum cout << diff; } // Driver Code int main() { // Given Input struct Node* head = NULL; insert(&head, 4); insert(&head, 3); insert(&head, 2); insert(&head, 1); int X = 3; // Function Call closestTripletSum(head, X); return 0; } |
Java
// Java program for the above approach class GFG { // Doubly linked list node static class Node { int data; Node next, prev; }; static Node head; // Function to insert a new node at // the beginning of doubly linked // list static void insert( int data) { // Allocate node Node temp = new Node(); // Fill the data value in it temp.data = data; temp.next = temp.prev = null ; // If head is null change // head to temp if ((head) == null ) { (head) = temp; } // Insert the node before head else { temp.next = head; (head).prev = temp; (head) = temp; } } // Function to find sum of triplet // closest to X static void closestTripletSum( int X) { // Points to the first node // of the triplet Node first = head; // Points to the second node // of the triplet Node second = head.next; // Stores the last node of // doubly linked list Node tail = head; // Traverse till end of the list while (tail.next != null ) { tail = tail.next; } // Stores the sum closest to X int diff = Integer.MAX_VALUE; // Points to the third node // of the triplet Node third = tail; // Iterate till the end of the list while (first != null ) { second = first.next; third = tail; while (second != null && third != null && third != second) { int sum = (first.data + second.data + third.data); // Check if the current sum // is closest to X if (Math.abs(X - sum) < Math.abs(X - diff)) { // Update the value of diff diff = sum; } // Check if sum is less than X if (sum < X) { // Increment the second // pointer second = second.next; } else { // Decrement the third // pointer third = third.prev; } } // Move the first pointer // ahead first = first.next; } // Print the closest sum System.out.print(diff); } // Driver Code public static void main(String[] args) { // Given Input head = null ; insert( 4 ); insert( 3 ); insert( 2 ); insert( 1 ); int X = 3 ; // Function Call closestTripletSum(X); } } // This code is contributed by umadevi9616 |
Python3
# Python program for the above approach import sys # Doubly linked list Node class Node: def __init__( self ): self .data = 0 ; self . next = None ; self .prev = None ; head = None ; # Function to insert a new Node at # the beginning of doubly linked # list def insert(data): # Allocate Node temp = Node(); # Fill the data value in it temp.data = data; temp. next = temp.prev = None ; # If head is None change # head to temp global head; if ((head) = = None ): (head) = temp; # Insert the Node before head else : temp. next = head; (head).prev = temp; (head) = temp; # Function to find sum of triplet # closest to X def closestTripletSum(X): # Points to the first Node # of the triplet first = head; # Points to the second Node # of the triplet second = head. next ; # Stores the last Node of # doubly linked list tail = head; # Traverse till end of the list while (tail. next ! = None ): tail = tail. next ; # Stores the sum closest to X diff = sys.maxsize; # Points to the third Node # of the triplet third = tail; # Iterate till the end of the list while (first ! = None ): second = first. next ; third = tail; while (second ! = None and third ! = None and third ! = second): sum = (first.data + second.data + third.data); # Check if the current sum # is closest to X if ( abs (X - sum ) < abs (X - diff)): # Update the value of diff diff = sum ; # Check if sum is less than X if ( sum < X): # Increment the second # pointer second = second. next ; else : # Decrement the third # pointer third = third.prev; # Move the first pointer # ahead first = first. next ; # Print the closest sum print (diff); # Driver Code if __name__ = = '__main__' : # Given Input head = None ; insert( 4 ); insert( 3 ); insert( 2 ); insert( 1 ); X = 3 ; # Function Call closestTripletSum(X); # This code is contributed by umadevi9616 |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Doubly linked list node public class Node { public int data; public Node next, prev; }; static Node head; // Function to insert a new node at // the beginning of doubly linked // list static void insert( int data) { // Allocate node Node temp = new Node(); // Fill the data value in it temp.data = data; temp.next = temp.prev = null ; // If head is null change // head to temp if ((head) == null ) { (head) = temp; } // Insert the node before head else { temp.next = head; (head).prev = temp; (head) = temp; } } // Function to find sum of triplet // closest to X static void closestTripletSum( int X) { // Points to the first node // of the triplet Node first = head; // Points to the second node // of the triplet Node second = head.next; // Stores the last node of // doubly linked list Node tail = head; // Traverse till end of the list while (tail.next != null ) { tail = tail.next; } // Stores the sum closest to X int diff = int .MaxValue; // Points to the third node // of the triplet Node third = tail; // Iterate till the end of the list while (first != null ) { second = first.next; third = tail; while (second != null && third != null && third != second) { int sum = (first.data + second.data + third.data); // Check if the current sum // is closest to X if (Math.Abs(X - sum) < Math.Abs(X - diff)) { // Update the value of diff diff = sum; } // Check if sum is less than X if (sum < X) { // Increment the second // pointer second = second.next; } else { // Decrement the third // pointer third = third.prev; } } // Move the first pointer // ahead first = first.next; } // Print the closest sum Console.Write(diff); } // Driver Code public static void Main(String[] args) { // Given Input head = null ; insert(4); insert(3); insert(2); insert(1); int X = 3; // Function Call closestTripletSum(X); } } // This code is contributed by umadevi9616 |
Javascript
<script> // javascript program for the above approach // Doubly linked list node class Node { constructor(val = 0) { this .data = val; this .prev = null ; this .next = null ; } } var head; // Function to insert a new node at // the beginning of doubly linked // list function insert(data) { // Allocate node var temp = new Node(); // Fill the data value in it temp.data = data; temp.next = temp.prev = null ; // If head is null change // head to temp if ((head) == null ) { (head) = temp; } // Insert the node before head else { temp.next = head; (head).prev = temp; (head) = temp; } } // Function to find sum of triplet // closest to X function closestTripletSum(X) { // Points to the first node // of the triplet var first = head; // Points to the second node // of the triplet var second = head.next; // Stores the last node of // doubly linked list var tail = head; // Traverse till end of the list while (tail.next != null ) { tail = tail.next; } // Stores the sum closest to X var diff = Number.MAX_VALUE; // Points to the third node // of the triplet var third = tail; // Iterate till the end of the list while (first != null ) { second = first.next; third = tail; while (second != null && third != null && third != second) { var sum = (first.data + second.data + third.data); // Check if the current sum // is closest to X if (Math.abs(X - sum) < Math.abs(X - diff)) { // Update the value of diff diff = sum; } // Check if sum is less than X if (sum < X) { // Increment the second // pointer second = second.next; } else { // Decrement the third // pointer third = third.prev; } } // Move the first pointer // ahead first = first.next; } // Print the closest sum document.write(diff); } // Driver Code // Given Input head = null ; insert(4); insert(3); insert(2); insert(1); var X = 3; // Function Call closestTripletSum(X); // This code is contributed by umadevi9616 </script> |
6
Time Complexity: O(N2)
Auxiliary Space: O(1)