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
**Correction Required** public static boolean findPair(Node head, int k) { // Write your code here. } Java Compiler problem, expecting boolean but the test cases are designed for pair of integers.
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 .....Please Pick questions from leetcode or gfg ...Thank you!
Simple Python Solution Time Complexity: O(N) def findPairsWithGivenSumOptimal(head, target): temp = head ans = [] #find last node while(temp.next): temp = temp.next right = temp left = head while(left.data < right.data): num = left.data + right.data if num == target: ans.append([left.data, right.data]) left = left.next right = right.prev elif num > target: right = right.prev else: left = left.next return ans
public static ArrayList findPairsWithGivenSum(int target, Node head) { // code here Node left = head; Node right = findtail(head); ArrayList ans = new ArrayList(); while(left.data
yeah kind of. but that is only for returning the answer. its not actually getting used to solve the problem. so O(n) if we see it as a whole..but to solve the problem its O(1)
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?
@user-om1zx4ox4h Because, Consider this example 1 2 3 4 9 sum= 5 Now left is at starting node and right is at ending node. While checking the conditions, 1st time 1 + 9 = 10 It is greater than 5 So, decrement right pointer by 1. 2nd time, 1+ 4 = 5 It is equal to 5 . So, add it to the vector. And increment left pointer by 1 and decrement right pointer by 1. 3rd time, 2 + 3 = 5 It is equal to the 5. So, add it to the vector. And increment left pointer by 1 and decrement right pointer by 1. 4th time, left pointer is at node 3 and right pointer is at node 2 Actually left and right pointers are crossed. However sum is 5 But actually this is duplicate sum if still you want to add it you. And increment left pointer by 1 and decrement right pointer by 1. 5th time, Left is at 4 and right is at 1 Again add it if you want but it is duplicate. And increment left pointer by 1 and decrement right pointer by 1. Now left is at 9 and right is at nullptr but still we are adding it. This will raise run time error. Because of the above reason, We should consider as while(left
No the optimized approach doesn't work for duplicates since we're moving both left & right when the sum matches. In the actual problem on CodeStudio, it is mentioned that the sorted DLL contains DISTINCT positive integers.
//given a sorted Linkedlist #include 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 findPairs(Node* head, int k) { vector 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 data , else loop breaks while ( left->data < right->data) { //if we get the data == k if(left->data + right->data == k){ pair 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;
![[#2024MAMA] G-DRAGON - 무제(Untitled, 2014)+POWER+HOME SWEET HOME+뱅뱅뱅+FANTASTIC BABY | Mnet 241123 방송](http://i.ytimg.com/vi/Ox29z5Nf1Uk/mqdefault.jpg)
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
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
hey bro... wanna team up? we can encourage each other and we can have friendly competition spirit as well.
@@sereneguy1804can I join guys
@@BadisaShalivahana can i join?
@@sereneguy1804 can we ?
**Correction Required**
public static boolean findPair(Node head, int k) {
// Write your code here.
}
Java Compiler problem, expecting boolean but the test cases are designed for pair of integers.
yes
have u got the solution?
@@animeislob3620already posted here in above comment
@@mahimagautam1810 ohk thnx
great video striver
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 .....Please Pick questions from leetcode or gfg ...Thank you!
No one thinks about hashing 😅
// Bro i have done using Hashing
vector findPairs(Node* head, int k)
{
vectorvp;
Node* temp = head;
unordered_mapmp;
while(temp != nullptr)
{
int x = k-(temp -> data);
if(mp.find(x) != mp.end())
{
vp.push_back({x, temp->data});
}
else{
mp[temp->data]++;
}
temp = temp -> next;
}
return vp;
}
What is concept?
I did with hashing 😅
Hashing takes more space to compute the larger test cases
Simple Python Solution Time Complexity: O(N)
def findPairsWithGivenSumOptimal(head, target):
temp = head
ans = []
#find last node
while(temp.next):
temp = temp.next
right = temp
left = head
while(left.data < right.data):
num = left.data + right.data
if num == target:
ans.append([left.data, right.data])
left = left.next
right = right.prev
elif num > target:
right = right.prev
else:
left = left.next
return ans
what if the sorted array has repeated number , for eg: 1,2,3,3,4,5,5,6 target is 6
THANK YOU STRIVER
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 findPairsWithGivenSum(int target, Node head) {
// code here
Node left = head;
Node right = findtail(head);
ArrayList ans = new ArrayList();
while(left.data
for brute force and optimal approach we are saving pair of element which should be space complexity of O(N)?
yeah kind of. but that is only for returning the answer. its not actually getting used to solve the problem. so O(n) if we see it as a whole..but to solve the problem its O(1)
Superb sir
Understood : )
UNDERSTOOD;
Smart solution!
Understood✅🔥🔥
For brute force can we not do it in a single loop? And set conditions for when sum exceeds the key etc ..correct me if I'm wrong
Thank you striver
sir wont it be left->datadata as the while loops condition if sum=6 and left is at 3 and right is at 3 if their are repeatation of numbers
not possible bro, its given in the question that the values are distinct
Thank you Bhaiya
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?
yes i had the same doubt, i have dry run many test cases and its ~O(n/2), so yeah we're right 🤜🤛
@@animeislob3620 No its wrong in previous lectures he said that if two variables in loop are travelling then O(2*n/2) which becomes O(N)
understood :)
Hail Mary full of grace
Undertsood
wrote the same code before watching the video
Understood
Thanks
understood
space complexity in brute fore must be n because of extra data structure right?
yes
respect++;
Can you give code o brute force in java
It is a O(2N) solution. but the question in the Sheet asked us to solve it in O(N) and if i use this solution then it is asking me to reduce the TC.
theres no way to find the tail in O(1). check the sheet if the tail is already provided. then only we can reduce to O(N)
@@furor05 yap but it is not submitting.
@@furor05 we dont need to find the tail i think
i know there are distinct data; but why there is error in while(left !=right )
@user-om1zx4ox4h
Because,
Consider this example
1 2 3 4 9
sum= 5
Now left is at starting node and right is at ending node.
While checking the conditions,
1st time
1 + 9 = 10
It is greater than 5
So, decrement right pointer by 1.
2nd time,
1+ 4 = 5
It is equal to 5 .
So, add it to the vector.
And increment left pointer by 1 and decrement right pointer by 1.
3rd time,
2 + 3 = 5
It is equal to the 5.
So, add it to the vector.
And increment left pointer by 1 and decrement right pointer by 1.
4th time,
left pointer is at node 3 and right pointer is at node 2
Actually left and right pointers are crossed. However sum is 5
But actually this is duplicate sum if still you want to add it you.
And increment left pointer by 1 and decrement right pointer by 1.
5th time,
Left is at 4 and right is at 1
Again add it if you want but it is duplicate.
And increment left pointer by 1 and decrement right pointer by 1.
Now left is at 9 and right is at nullptr but still we are adding it. This will raise run time error.
Because of the above reason,
We should consider as
while(left
@@tejaswaniguttula5961thnks a lot bro...
GOD
US
god
IF we have duplicate vallues does this work
No the optimized approach doesn't work for duplicates since we're moving both left & right when the sum matches. In the actual problem on CodeStudio, it is mentioned that the sorted DLL contains DISTINCT positive integers.
#include
using namespace std;
struct node
{
int data;
node * next;
node * prev;
node(int data)
{
this->data=data;
next=NULL;
prev=NULL;
}
};
node * insertNodeInDoublyLinkedList(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
Node* findTail(Node* head) {
Node* tail = head;
while (tail->next != NULL)
tail = tail->next;
return tail;
}
vector findPairs(Node* head, int k) {
vector 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;
}
//given a sorted Linkedlist
#include
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 findPairs(Node* head, int k)
{
vector 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 data , else loop breaks
while ( left->data < right->data)
{
//if we get the data == k
if(left->data + right->data == k){
pair 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;
}
thank you bhaiya
Understood
understood
Understood
understood
Understood
understood
Understood
understood
Understood
understood
understood
understood