Find the Minimum and Maximum Number of Nodes Between Critical Points
Problem
A critical point is a node (not head or tail) whose value is strictly greater than both neighbors (local max) or strictly less than both (local min). Return [minDistance, maxDistance] between any two critical points; return [-1, -1] if fewer than two exist.
head = [5, 3, 1, 2, 5, 1, 2][1, 3]def nodes_between_critical_points(head):
first = last = -1
min_dist = float("inf")
prev_idx = -1
prev = head
cur = head.next
i = 1
while cur and cur.next:
if (cur.val > prev.val and cur.val > cur.next.val) or \
(cur.val < prev.val and cur.val < cur.next.val):
if first == -1:
first = i
else:
min_dist = min(min_dist, i - prev_idx)
last = i
prev_idx = i
prev = cur
cur = cur.next
i += 1
if first == last:
return [-1, -1]
return [min_dist, last - first]function nodesBetweenCriticalPoints(head) {
let first = -1, last = -1, minDist = Infinity, prevIdx = -1;
let prev = head, cur = head.next, i = 1;
while (cur && cur.next) {
const isMax = cur.val > prev.val && cur.val > cur.next.val;
const isMin = cur.val < prev.val && cur.val < cur.next.val;
if (isMax || isMin) {
if (first === -1) first = i;
else minDist = Math.min(minDist, i - prevIdx);
last = i;
prevIdx = i;
}
prev = cur;
cur = cur.next;
i++;
}
if (first === last) return [-1, -1];
return [minDist, last - first];
}class Solution {
public int[] nodesBetweenCriticalPoints(ListNode head) {
int first = -1, last = -1, minDist = Integer.MAX_VALUE, prevIdx = -1;
ListNode prev = head, cur = head.next;
int i = 1;
while (cur != null && cur.next != null) {
boolean isMax = cur.val > prev.val && cur.val > cur.next.val;
boolean isMin = cur.val < prev.val && cur.val < cur.next.val;
if (isMax || isMin) {
if (first == -1) first = i;
else minDist = Math.min(minDist, i - prevIdx);
last = i;
prevIdx = i;
}
prev = cur;
cur = cur.next;
i++;
}
if (first == last) return new int[]{-1, -1};
return new int[]{minDist, last - first};
}
}vector<int> nodesBetweenCriticalPoints(ListNode* head) {
int first = -1, last = -1, minDist = INT_MAX, prevIdx = -1;
ListNode* prev = head;
ListNode* cur = head->next;
int i = 1;
while (cur && cur->next) {
bool isMax = cur->val > prev->val && cur->val > cur->next->val;
bool isMin = cur->val < prev->val && cur->val < cur->next->val;
if (isMax || isMin) {
if (first == -1) first = i;
else minDist = min(minDist, i - prevIdx);
last = i;
prevIdx = i;
}
prev = cur;
cur = cur->next;
i++;
}
if (first == last) return {-1, -1};
return {minDist, last - first};
}Explanation
A critical point is any node (not the head or tail) that is either bigger than both of its neighbors (a local max) or smaller than both (a local min). We want the smallest and largest distance between any two critical points, in a single walk through the list.
The key realization is that you only ever need three numbers as you scan: the index of the first critical point you saw, the last one so far, and the previous one. The maximum gap is always between the very first and very last critical points, while the minimum gap can only happen between two neighboring critical points.
So we slide a cur pointer through the interior nodes, checking each against prev and cur.next. When we hit a critical point at index i: if it is the first, we record first = i; otherwise we update min_dist = min(min_dist, i - prev_idx) using the gap to the previous critical point. Either way we update last = i and prev_idx = i.
At the end, if first == last there was at most one critical point, so we return [-1, -1]. Otherwise the answer is [min_dist, last - first].
Example: [5, 3, 1, 2, 5, 1, 2] has critical points at index 2 (min), 4 (max), and 5 (min). The closest pair is indices 4 and 5 (gap 1), and the farthest is 2 and 5 (gap 3), giving [1, 3].