Find the Minimum and Maximum Number of Nodes Between Critical Points
Asked 3 months ago
0Comments
1 Views
Input: head = [5,3,1,2,5,1,2]
Output: [1,3]
Explanation: There are three critical points:-
- [5,3,1,2,5,1,2]: The third node is a local minima because 1 is less than 3 and 2.
- [5,3,1,2,5,1,2]: The fifth node is a local maxima because 5 is greater than 2 and 1.
- [5,3,1,2,5,1,2]: The sixth node is a local minima because 1 is less than 5 and 2.
The minimum distance is between the fifth and the sixth node. minDistance = 6 - 5 = 1.
The maximum distance is between the third and the sixth node. maxDistance = 6 - 3 = 3.
Image credits : LEETCODE
GENERAL IMPLEMENTATION !
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
// Definition for singly-linked list node
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
vector<int> nodesBetweenCriticalPoints(ListNode* head) {
vector<int> ans = {-1, -1}; // stores Min and Max Distance
// We need at least 3 nodes to have a critical point
ListNode* prev = head;
if (!prev) return ans;
ListNode* curr = head->next;
if (!curr) return ans;
ListNode* nxt = head->next->next;
if (!nxt) return ans;
int firstCP = -1;
int lastCP = -1;
int minDistance = INT_MAX;
int i = 1;
while (nxt) {
// Check if current node is a critical point
bool isCP = ((curr->val > prev->val && curr->val > nxt->val) ||
(curr->val < prev->val && curr->val < nxt->val));
if (isCP) {
if (firstCP == -1) {
// First critical point found
firstCP = i;
lastCP = i;
} else {
// Update min distance and last critical point
minDistance = min(minDistance, i - lastCP);
lastCP = i;
}
}
// Move to next set of nodes
++i;
prev = prev->next;
curr = curr->next;
nxt = nxt->next;
}
if (lastCP == firstCP) {
// Only 1 critical point found
return ans;
} else {
ans[0] = minDistance;
ans[1] = lastCP - firstCP;
}
return ans;
}
};
// Function to print the linked list
void print(ListNode *head) {
ListNode *temp = head;
while (temp != NULL) {
cout << temp->val << " ";
temp = temp->next;
}
cout << endl;
}
int main() {
// Create the linked list: 5 -> 3 -> 1 -> 2 -> 5 -> 1 -> 2
ListNode *head = new ListNode(5);
head->next = new ListNode(3);
head->next->next = new ListNode(1);
head->next->next->next = new ListNode(2);
head->next->next->next->next = new ListNode(5);
head->next->next->next->next->next = new ListNode(1);
head->next->next->next->next->next->next = new ListNode(2);
// Print the linked list
cout << "Linked List: ";
print(head);
// Create a Solution object
Solution sol;
// Find the minimum and maximum number of nodes between critical points
vector<int> result = sol.nodesBetweenCriticalPoints(head);
// Print the result
cout << "Minimum distance between critical points: " << result[0] << endl;
cout << "Maximum distance between critical points: " << result[1] << endl;
// Free the allocated memory (not necessary in this case, but good practice)
ListNode *temp;
while (head != nullptr) {
temp = head;
head = head->next;
delete temp;
}
return 0;
}Didn't Understood ! ?
LET ME EXPLAIN DOSTH !
First ! we initialize the answer vector with -1 for both min and max distance.
vector<int> nodesBetweenCriticalPoints(ListNode* head) {
vector<int> ans = {-1,-1}; // stores Min and Max Distance !next !
This block checks if we have at least 3 nodes. If not, we return the default answer.
// in order to check critical Points we must have 3 Nodes !
ListNode* prev = head; // if only 1 Node exists !
if(!prev) return ans;
ListNode* curr = head->next; // 2 Nodes !
if(!curr) return ans;
ListNode* nxt = head->next->next; // 3 Nodes !
if(!nxt) return ans;We initialize variables to keep track of the first and last critical points, the minimum distance between critical points, and the current index.
prev -> curr -> nxt
| | |
v v v
[5] -> [3] -> [1] -> [2] -> [5] -> [1] -> [2]Next Step :
We iterate through the list, checking if the current node is a critical point.
while(nxt) {
bool isCP = ((curr->val > prev->val && curr->val > nxt->val) ||
(curr->val < prev->val && curr->val < nxt->val)) ? true : false;We iterate through the list, checking if the current node is a critical point
isCP?
|
prev -> curr -> nxt
| | |
v v v
[5] -> [3] -> [1] -> [2] -> [5] -> [1] -> [2]If we find a critical point, we update our tracking variables.
if(isCP && firstCP == -1) {
firstCP = i;
lastCP = i;
} else if(isCP) {
minDistance = min(minDistance, i - lastCP);
lastCP = i;
}We move to the next set of nodes and continue the process
++i;
prev = prev->next;
curr = curr->next;
nxt = nxt->next;Finally, we set the answer based on our findings. If we found only one critical point, we return the default answer. Otherwise, we return the minimum distance and the distance between the first and last critical points.
if(lastCP == firstCP) {
// Only 1 CP Point Found !
return ans;
} else {
ans[0] = minDistance;
ans[1] = lastCP - firstCP;
}
return ans;
}Complete Visualization :
Step 1: [5] -> [3] -> [1] -> [2] -> [5] -> [1] -> [2]
^ ^ ^
prev curr nxt
i = 1, not a CP
Step 2: [5] -> [3] -> [1] -> [2] -> [5] -> [1] -> [2]
^ ^ ^
prev curr nxt
i = 2, CP found (firstCP = 2, lastCP = 2)
Step 3: [5] -> [3] -> [1] -> [2] -> [5] -> [1] -> [2]
^ ^ ^
prev curr nxt
i = 3, not a CP
Step 4: [5] -> [3] -> [1] -> [2] -> [5] -> [1] -> [2]
^ ^ ^
prev curr nxt
i = 4, CP found (lastCP = 4, minDistance = 2)
Step 5: [5] -> [3] -> [1] -> [2] -> [5] -> [1] -> [2]
^ ^ ^
prev curr nxt
i = 5, CP found (lastCP = 5, minDistance = 1)
Final: ans = [1, 3] (minDistance = 1, lastCP - firstCP = 5 - 2 = 3)The final result is a linked list where each node represents the sum of non-zero elements between zeros in the original list.
This solution efficiently merges the nodes by using two pointers:
The 'slow' pointer moves to each position where a sum should be placed.
The 'fast' pointer iterates through all nodes, accumulating the sum.
When 'fast' reaches a zero, it signals the end of a group, so we update the node at 'slow' with the accumulated sum, move 'slow' to the next position, and reset the sum.
The algorithm effectively creates a new list in-place by overwriting the necessary nodes and then truncating the list at the last required node.
medium
Share