Link to Question

MEDIUM

2058. Find the Minimum and Maximum Number of Nodes Between Critical Points

You are given a linked list of integers. A node is a critical point if it is either a local maxima or minima. Return the minimum and maximum number of nodes between any two critical points. If there are fewer than two critical points, return [-1, -1].

Example

Input:

head = [1,3,2,2,3,2,2,2,7]

Output:

[3, 3]

Explanation: There are three critical points at positions 2, 5, and 8. The minimum and maximum distances are both 3.

---

Constraints

• The number of nodes in the list is in the range [3, 10^5].
• 1 <= Node.val <= 10^5

---

Solution: One Pass

• Time Complexity: O(n), where n is the number of nodes in the list.
• Space Complexity: O(n), for storing critical point indices.

C++

class Solution {
public:
    vector<int> nodesBetweenCriticalPoints(ListNode* head) {
        vector<int> pos;
        int idx = 1;
        ListNode *prev = head, *curr = head->next;
        while (curr && curr->next) {
            if ((curr->val > prev->val && curr->val > curr->next->val) ||
                (curr->val < prev->val && curr->val < curr->next->val)) {
                pos.push_back(idx);
            }
            prev = curr;
            curr = curr->next;
            idx++;
        }
        if (pos.size() < 2) return {-1, -1};
        int minDist = INT_MAX, maxDist = pos.back() - pos.front();
        for (int i = 1; i < pos.size(); ++i) {
            minDist = min(minDist, pos[i] - pos[i-1]);
        }
        return {minDist, maxDist};
    }
};