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

Scan the list once, comparing each node with its neighbours. The maximum distance is always between the first and last critical point; the minimum is the smallest gap between consecutive ones.

Idea

A node is a critical point only if it has both a previous and next neighbour and is a strict local maximum or minimum. So we can decide whether a node is critical just by looking at the triple (prev, cur, next).

As we walk the list we only need to remember two positions:

• first — the index of the first critical point we saw.
• prev — the index of the previous critical point (the most recent one before the current).

The key observations:

• maxDistance is always lastCritical - first — the two farthest critical points are the first and the last one, so we just keep updating with the newest critical index.
• minDistance is the smallest gap between two consecutive critical points. The closest pair can only be adjacent in the ordered list of critical indices, so comparing each new critical point against the immediately preceding one is enough.

If we end with fewer than two critical points, the answer is [-1, -1].

Walk-through

Take head = [5,3,1,2,5,1,2] (0-indexed positions, the problem counts nodes from 1 so distances use 1-based positions):

1. Node at position 3 (value 1) is a local minima (1 < 3 and 1 < 2). It is the first critical point → first = 3, prev = 3.
2. Node at position 5 (value 5) is a local maxima (5 > 2 and 5 > 1). minDist = min(inf, 5 - 3) = 2, maxDist = 5 - 3 = 2, then prev = 5.
3. Node at position 6 (value 1) is a local minima (1 < 5 and 1 < 2). minDist = min(2, 6 - 5) = 1, maxDist = 6 - 3 = 3, then prev = 6.

Result: [1, 3].

Why one pass suffices

We never revisit a node, and each node does O(1) work (a couple of comparisons and two min/subtraction updates). The list is scanned exactly once.

Complexity

• Time: O(n) — a single traversal of the list.
• Space: O(1) — only a handful of indices are tracked.

class Solution {
    public int[] nodesBetweenCriticalPoints(ListNode head) {
        int first = -1;          // position of the first critical point (1-based)
        int prevCrit = -1;       // position of the previous critical point
        int minDist = Integer.MAX_VALUE;
        int maxDist = -1;

        int pos = 2;             // position of `cur`, starting at the second node
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null && cur.next != null) {
            if ((cur.val > prev.val && cur.val > cur.next.val) ||
                (cur.val < prev.val && cur.val < cur.next.val)) {
                if (first == -1) {
                    first = pos;
                } else {
                    minDist = Math.min(minDist, pos - prevCrit);
                    maxDist = pos - first;
                }
                prevCrit = pos;
            }
            prev = cur;
            cur = cur.next;
            pos++;
        }

        if (maxDist == -1) {
            return new int[]{-1, -1};
        }
        return new int[]{minDist, maxDist};
    }
}