L19. Find all Pairs with given Sum in DLL

Please do give us a like, and subscribe to us if you are new to our channel.

[monishrainy]

Thank You stiver. I am able to come up with the intuition on my own. I have completed all the LinkedList question. Thank you for your help

[mahimagautam]

**Correction Required**

public static boolean findPair(Node<Integer> head, int k) {
// Write your code here.
}

Java Compiler problem, expecting boolean but the test cases are designed for pair of integers.

[moonlight-tded]

i was following your strivers playlist (a-z sde sheet) and did most of the linked list questions entirely by myself without watching soln videos, thanks to you brother, its been 10 days and I have solved 125 / 455

[Factzspeaker]

A request to Striver, please donot take all questions from code studio ....They donot accept java solutions always, like in this prob they have given a boolean function to return the pair of nodes, their are also class related error when java code is submitted, The same code works on other coding platforms but not on code studio Pick questions from leetcode or gfg ...Thank you!

[soumyadeepsaha]

sir wont it be left->data<=right->data as the while loops condition if sum=6 and left is at 3 and right is at 3 if their are repeatation of numbers

[MJBZG]

wrote the same code before watching the video

[rpgnqiw]

Can you give code o brute force in java

[sahelidebnath]

for while loop, it may traversing all the nodes but overall while loop will run for n/2 times.
Please let me know whether my understanding is correct or not?

[omzxoxh]

i know there are distinct data; but why there is error in while(left !=right )

[aditiapar]

space complexity in brute fore must be n because of extra data structure right?

[jagadeeshp]

IF we have duplicate vallues does this work

[mahimagautam]

GFG Soln:


class Solution {

public static Node findtail(Node head) {
Node temp = head;
while(temp.next!=null){
temp = temp.next;
}
return temp;
}


public static ArrayList<ArrayList<Integer>> findPairsWithGivenSum(int target, Node head) {
// code here

Node left = head;
Node right = findtail(head);
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();

while(left.data <right.data){
ArrayList<Integer> pair = new ArrayList<>();
if(left.data + right.data == target ){
pair.add(left.data);
pair.add(right.data);
ans.add(pair);
left= left.next;
right= right.prev;
}

else if(left.data + right.data < target){
left = left.next;
}
else{
right = right.prev;
}
}
return ans;
}
}

[deepanshusoni]

#include<iostream>
using namespace std;
struct node
{
int data;
node * next;
node * prev;

node(int data)
{
this->data=data;
next=NULL;
prev=NULL;

}
};

node * head, int data) {
node* newnode = new node(data);

if (head != NULL) {
newnode->next = head;
head->prev = newnode;

}

head = newnode;
newnode->prev = NULL;

return head;
}

node * pairofsum(node * head, int n )
{
if(head==NULL || n==0) return head;
node * newlisthead=NULL;
node * temp=head;

int sum=0;
while (temp->next!=nullptr)
{
node *temp1=temp->next;
while(temp1 !=NULL )
{
sum=temp->data+temp1->data;

if(n==sum)
{
newlisthead=insertNodeInDoublyLinkedList(newlisthead, temp->data);
newlisthead=insertNodeInDoublyLinkedList(newlisthead, temp1->data);

}
temp1=temp1->next;

}
temp=temp->next;

}


return newlisthead;

}

void printdoublylist(node * head)
{
node *temp=head;
while(temp!=NULL)
{
cout<<temp->data<<endl;
temp=temp->next;

}

}


int main()
{
node * head=NULL;
head=insertNodeInDoublyLinkedList(head, 1);
head=insertNodeInDoublyLinkedList(head, 2);
head=insertNodeInDoublyLinkedList(head, 3);
head=insertNodeInDoublyLinkedList(head, 4);
head=insertNodeInDoublyLinkedList(head, 5);
head=pairofsum(head, 5);
printdoublylist(head);


}

here is the fulll code
but its complexity is equal to near to n^2;
optimise it 😁😁

[jeevanreddy]

Node* findTail(Node* head) {
Node* tail = head;
while (tail->next != NULL)
tail = tail->next;
return tail;
}

vector<pair<int, int>> findPairs(Node* head, int k) {
vector<pair<int, int>> ans;
if (head == NULL)
return ans;

Node* left = head;
Node* right = findTail(head);

while (left->data < right->data) {
if (left->data + right->data == k) {
ans.push_back({left->data, right->data});
left = left->next;
right = right->prev;
} else if (left->data + right->data < k) {
left = left->next;
} else {
right = right->prev;
}
}

return ans;
}

[techtuber]

//given a sorted Linkedlist

#include<bits/stdc++.h>
using namespace std;

//Node class
class Node {
public:
int data;
Node *prev;
Node *next;
Node() {
this->data = 0;
this->prev = NULL;
this->next = NULL;
}
Node(int data) {
this->data = data;
this->prev = NULL;
this->next = NULL;
}
Node (int data, Node *next, Node *prev) {
this -> data = data;
this -> prev = prev;
this -> next = next;
}
};


//we will perform two pointer approach
vector<pair<int, int>> findPairs(Node* head, int k)
{
vector<pair<int, int>> ans;
//putting two pointer
Node* left = head;
Node* right = head;

//now placing right pointer to the end of LL
while(right->next != nullptr){
right = right->next;
}

//now loop will run till = left->data <= right->data, else loop breaks
while ( left->data < right->data)
{
//if we get the data == k
if(left->data + right->data == k){
pair<int, int> p;
p.first = left->data;
p.second = right->data;
ans.push_back(p);

//moving ptr together
left = left->next;
right = right->prev;
}
//sum is > k
else if(left->data + right->data > k){
right = right->prev;//move right one less
}
else{
//sum is < k
left = left->next;
}
}
return ans;

}