Find the Minimum and Maximum Number of Nodes Between Critical Points | 2 Ways | Leetcode 2058

Whatsapp Community Link : www.whatsapp.com/channel/0029...
This is the 26th Video of our Playlist "Linked List : Popular Interview Problems" by codestorywithMIK
In this video we will try to solve a good practice problem on Linked List : Find the Minimum and Maximum Number of Nodes Between Critical Points | 2 Ways | Leetcode 2058 | codestorywithMIK
I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.
Problem Name : Find the Minimum and Maximum Number of Nodes Between Critical Points | 2 Ways | Leetcode 2058 | codestorywithMIK
Company Tags : META, AMAZON
My solutions on Github(C++ & JAVA) : github.com/MAZHARMIK/Intervie...
Leetcode Link : leetcode.com/problems/find-th...
My DP Concepts Playlist : • Roadmap for DP | How t...
My Graph Concepts Playlist : • Graph Concepts & Qns -...
My Recursion Concepts Playlist : • Introduction | Recursi...
My GitHub Repo for interview preparation : github.com/MAZHARMIK/Intervie...
Instagram : / codestorywithmik
Facebook : / 100090524295846
Twitter : / cswithmik
Subscribe to my channel : / @codestorywithmik
Summary :
Approach 1 (Using Simple Looping)
Time Complexity (T.C): O(n)
Space Complexity (S.C): O(1)
Description:
This approach uses two pointers to traverse the linked list while maintaining a record of the previous node and current node.
It checks if the current node is a critical point by comparing its value with the previous and next nodes.
If a critical point is found, it updates the minimum distance (minDistance) and stores the indices of the first and previous critical points.
At the end of the traversal, it calculates the maximum distance between the first and the last critical points.
If no critical points are found, it returns {-1, -1}; otherwise, it returns the minimum and maximum distances between the critical points.
Approach 2 (Similar Code but Simple)
Time Complexity (T.C): O(n)
Space Complexity (S.C): O(1)
Description:
This approach is similar to the first one but simplifies the logic by directly comparing the values of the previous, current, and next nodes during traversal.
It uses three variables (prevValue, currValue, nextValue) to hold the values of the nodes, and it updates these values as it traverses the list.
Critical points are identified by checking if the current node's value is either a local minimum or maximum compared to its neighbors.
It keeps track of the first and previous critical points and updates the minimum distance (minDistance).
The result array is updated with the minimum and maximum distances between critical points.
If no critical points are found, it returns {-1, -1}.
Both approaches effectively traverse the list in linear time and maintain a constant space complexity, making them efficient solutions for finding the distances between critical points in a linked list.
╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝
✨ Timelines✨
00:00 - Introduction
#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #newyear2024

[@vivekingle1898]

Bhai aapke wajese leetcode solve karne ki aadat lag gayi🙃

[@karanpartap2769]

same bro

[@NiteshYadavnitw]

@@karanpartap2769 @vivekingle1898 to leave lelo, aur rest karo

[@aws_handles]

Same

[@wearevacationuncoverers]

same bro

[@ayaanrashid960]

i thought I'm the only one who listen this song while solving leetcode

[@user-ip9kr9nz9t]

"Pehele Majboori mein shuru kiye thee , abb mazaaa araha hai " - apki wajah se bhaiya

[@mr.unlucky4954]

Bro Thanks for this and could you please upload by 9 am please

[@user13443fg]

Second approach have lot of variables. This way, it can be done using lesser variables.
class Solution {
public:
vector nodesBetweenCriticalPoints(ListNode* head) {
vectorans{INT_MAX,INT_MIN};
int idx = 2;
ListNode* prev = head;
head = head->next;

int first = -1,consec = -1;
while(head && head->next){
if((head->val > prev->val && head->val > head->next->val) || (head->val < prev->val && head->val < head->next->val))
{
if(first == -1){
first = consec = idx;
}else{
ans[0] = min(ans[0],idx-consec);
ans[1] = max(ans[1],idx-first);
consec = idx;
}
}
idx++;
prev = head;
head=head->next;
}

if(first == consec)
return {-1,-1};
return ans;
}
};

[@RanitBarua]

nice explanation bro

[@gauravbanerjee2898]

Thanks a lot bhaiya ❤❤

[@aws_handles]

Thanks. Within just 5 minutes in the video, i stopped and coded it

[@Coder_Buzz07]

Best explanation ever😊

[@gui-codes]

bhai maza agya. maine khud se code karliya.

[@dayashankarlakhotia4943]

Good explanation 👏 👍

[@Inspire_with_SM]

bhaiya kuch dino se mera comment mey jo bhi kar rha hu wah delete ho ja rha hai pata nahi aisa q ho rha tha but i think ab thik ho gya hai .
😊😊

[@ugcwithaddi]

Good one ☝️.
I solved similar to 2nd way

[@fenilpatel6238]

Kya hum list ke elements ko array me store karane ke bad local minima and maxima find karake minimum and maximum distance ka pair return kar sakate hai????

[@adityarai9039]

bhaiya aapke second approach mane pahle laga de the😌

[@shabananoor9423]

❤❤

[@user-vs5rh1oz3w]

bhai online assessment ke liye playlist banado please

[@manishgaming4638]

Easy Question if u are familiar with linked list.
Solved on my own

[@factinsaan4333]

My Approach
class Solution {
public:
vector nodesBetweenCriticalPoints(ListNode* head) {
int maxi=INT_MIN,first;
ListNode*temp=head;
ListNode*temp1=head->next; ListNode*temp2=head->next->next;
int index=1,mini=INT_MAX,prev=INT_MAX,f=1;
while(temp2){
if((temp->valval&&temp1->val>temp2->val)||(temp->val>temp1->val&&temp1->valval)){
if(f==1){
first=index;
f=0;
}

if(index>=prev)
mini=min(mini,index-prev);
maxi=max(maxi,index-prev);
prev=index;
}
index++;
temp2=temp2->next;
temp1=temp1->next;
temp=temp->next;
}
if(maxi==INT_MIN||mini==INT_MAX)
return {-1,-1};
maxi=prev-first;
return {mini,maxi};
}
};

[@dipalisharma4682]

1st comment 🎉🎉❤

[@user-ym1nv1pw8i]

Second 😅

[@dipalisharma4682]

@user-ym1nv1pw8i yup actually 😅

[@Shivamsingh-ry6bz]

winner

[@gui-codes]

third 😂

[@user-ym1nv1pw8i]

@@gui-codes 😂

[@Inspire_with_SM]

bhaiya, my Approach -->
class Solution {
public int[] nodesBetweenCriticalPoints(ListNode head) {
// Base Case
if(head.next.next == null) return new int[] {-1 ,-1};
// // Declare a result array
// int[] result = new int[2];
// Arrays.fill(result, -1);

ListNode prev = head;
ListNode curr = head.next; // prev.next
ListNode front = curr.next; // head.next.next
int counter = 2;

List position = new ArrayList();
while(front != null){
if((curr.val > prev.val && curr.val > front.val) || (curr.val < prev.val && curr.val < front.val)){
position.add(counter);
}
prev = curr;
curr = front;
front = front.next;
counter++;
}

if(position.size() < 2){
return new int[] {-1, -1};
}

int[] arr = new int[position.size()];
for(int i=0; i

[@SumitKumar_4549]

Why are you using an extra array even though you are list??

[@learn_in_shorts]

Wah galti se kar diya tha baad mey correct kiya mey but old code hi copy Kiya tha to wah ji paste kar diya yaha pr 😊

[@harshshukla9634]

lmao bro ..i used the same logic as you do seee
class Solution {
public:
int findmin(vector &maxmin){
int mini = INT_MAX;
for(int i = 1;inext==nullptr||head->next->next==nullptr){
return {-1,-1};
}
vectormaxmin;
int count = 2;
ListNode* pre = head;
ListNode* cur = head->next ;
ListNode* sc =cur ->next ;
while(sc!=nullptr){
if((cur->val>sc->val&&cur->val>pre->val) || (cur->valval&&cur->valval) ){
maxmin.push_back(count);
}
pre = pre->next;
cur= cur->next;
sc=sc->next;
count++;
}
if(maxmin.size()

[@mohitchoudhary7234]

But khud se approach nhj aarhi😢😢 kya kru

[@utkarshsahay9908]

class Solution {
public:
vector nodesBetweenCriticalPoints(ListNode* head) {
vector ans = {-1,-1};
ListNode* p = head;
ListNode* c = head->next;
ListNode* n = head->next->next;
int idx = 1,fidx = -1,sidx = -1,mini = INT_MAX,maxi = INT_MIN;
while(n){
if((c->val > p->val && c->val > n->val) || (c->val < p->val && c->val < n->val)){
if(sidx == -1) sidx = idx;
if(fidx == -1) fidx = idx;
else{
mini = min(mini,idx-sidx);
maxi = max(maxi,idx-fidx);
}
sidx = idx;
}
idx++;
n = n->next;
c = c->next;
p = p->next;
}
if(mini != INT_MAX) ans[0] = mini;
if(maxi != INT_MIN) ans[1] = maxi;
return ans;
}
};❤❤

[@tusharnanda3885]

class Solution {
public:
using Node = ListNode;
vector nodesBetweenCriticalPoints(ListNode* head) {
int a = -1;
int b = -1;
Node *prev = 0;
Node *temp = head;
vector ans = {INT_MAX , INT_MIN};
int cnt = 0;
while(temp)
{
cnt++;
if(prev && temp->next)
{
int v1 = prev->val;
int v2 = temp->next->val;
int v = temp->val;
if((v1v2 ) || (v1> v && vnext;
}
if(ans[0] == INT_MAX) return {-1,-1};
return ans;
}
};

[@aizad786iqbal]

class Solution {
public int[] nodesBetweenCriticalPoints(ListNode head) {
TreeSet tset = new TreeSet();

ListNode temp = head.next;
ListNode prev = head;
int c=2;
while(temp.next!=null){
int prevVal = prev.val;
int currVal = temp.val;
int nextVal = temp.next.val;
System.out.println();
if((prevVal < currVal && nextVal < currVal) || (prevVal > currVal && nextVal > currVal)){
tset.add(c);
}
prev=temp;
temp=temp.next;
c++;
}

int res[] = new int[2];
res[0] = -1;
res[1] = -1;
if(tset!= null && !tset.isEmpty() && tset.size() >= 2){
int minDiff = Integer.MAX_VALUE;

Iterator itr = tset.iterator();
int min = itr.next();
int prevEle = min;
while(itr.hasNext()){
int currEle = itr.next();
minDiff = Math.min(minDiff, currEle-prevEle);
prevEle=currEle;
}
int max = prevEle;

res[0] = minDiff;
res[1] = max - min;
}
return res;
}
}
I came up with this solution on my own
somehow Leetcode showed TC -- O(N) ....
yet mera solution to 1200 ms kuch ka hua :)

[@aizad786iqbal]

nvm it was because of
System.out.println();
it works fine without it as well
60 ms and removing treeset , it went to 4 ms

[@Tejas-Coder]

My Solution [Java]
class Solution {
public int[] nodesBetweenCriticalPoints(ListNode head) {
int[] ans = new int[2];
Arrays.fill(ans, -1);
if (head == null || head.next == null || head.next.next == null)
return ans;
ListNode prev = head;
ListNode curr = head.next;
int index = 1;
int minDist = Integer.MAX_VALUE;
int firstCritical = -1;
int lastCritical = -1;
while(curr.next != null) {
if((prev.val > curr.val && curr.next.val > curr.val)
|| (prev.val < curr.val && curr.next.val < curr.val)) {
if(firstCritical == -1) firstCritical = index;
else minDist = Math.min(minDist, index - lastCritical);
lastCritical = index;
}
prev = curr;
curr = curr.next;
index++;
}
if (firstCritical != -1 && lastCritical != -1 && firstCritical != lastCritical) {
ans[0] = minDist;
ans[1] = lastCritical - firstCritical;
}
return ans;
}
}

[@AryanVats603]

Today's ques was easy one.. Solved it by myself 🥹