No result illustrationNo result illustration

DevLoom

search

Lets Connect

chevron right
Menu
Home

Home

Community

Community

Blog Posts

Blog Posts

Programming

Programming

Tech Topics

Tech Topics

Explore

Explore

Find Jobs

Find Jobs

Tags

Tags

DevLoomPerfect Place for devs
    profile

    Jubair

    upvoteupvote

    0

    downvote

    0

    star

    Find the Minimum and Maximum Number of Nodes Between Critical Points

    clock icon

    Asked 1 year ago

    message

    0Comments

    eye

    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.

     

    LinkedList
    must
    medium

    Share

    Write your comment here !

    0 Responses