Find the Minimum and Maximum Number of Nodes Between Critical Points

summary

• Finding critical points in a linked list and calculating the minimum and maximum distances between them.

approach

• The approach used is to traverse the linked list and keep track of the previous node's value
• When a new node is encountered, it checks if the current node and the next node have the same value
• If they do not, and the current node's value is greater than the previous node's value, or less than the previous node's value, it checks if the current node is a local maxima or minima
• If it is, it adds the current index to the vector of nodes between critical points
• The minimum distance is calculated by finding the minimum difference between any two indices in the vector, and the maximum distance is calculated by finding the maximum difference between any two indices in the vector.

complexity

• O(n), where n is the number of nodes in the linked list

explain

• The code first initializes a variable `prev` to -1 to keep track of the previous node's value
• It then traverses the linked list, and for each node, it checks if the current node and the next node have the same value
• If they do not, and the current node's value is greater than the previous node's value, or less than the previous node's value, it checks if the current node is a local maxima or minima
• If it is, it adds the current index to the vector of nodes between critical points
• The minimum distance is calculated by finding the minimum difference between any two indices in the vector, and the maximum distance is calculated by finding the maximum difference between any two indices in the vector
• If there are fewer than two critical points, the function returns [-1, -1].

Solution Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int prev = -1;
    vector nodesBetweenCriticalPoints(ListNode* head) {
        ListNode* ptr;
        vector ansVector;
        int minVal = 1234567890;
        int idx;
        for(ptr = head, idx=0; ptr->next != nullptr; ptr = ptr->next, idx++){
            if(prev == -1){
                prev = ptr->val;
                continue;
            }
            if (ptr->next->val > ptr->val && prev > ptr->val){
                if (!ansVector.empty()){
                    minVal = min(minVal, idx - ansVector.back());
                }
                ansVector.push_back(idx);
            } else if(ptr->next->val < ptr->val && prev < ptr->val){
                if (!ansVector.empty()){
                    minVal = min(minVal, idx - ansVector.back());
                }
                ansVector.push_back(idx);
            }
            prev = ptr->val;
        }
        if (ansVector.size() < 2) return {-1, -1};
        return {minVal, ansVector.back() - ansVector[0]};
    }
};