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

Problem Overview

A critical point is a node whose value is a strict local maximum or minimum compared with its neighbors.

Intuition

A critical point is a node whose value is a strict local maximum or minimum compared with its neighbors. You need the smallest and largest number of nodes between two critical points, measured by index distance. One left-to-right pass is enough: remember the first critical index, update the minimum gap whenever you see another critical point, and at the end the maximum gap is last minus first.

Algorithm

1Start with prev at head and curr at head.next. index counts nodes from the head.
2While curr.next is not null, check whether curr is a peak or valley.
3On the first critical point, store its index. On later ones, update minDistance with index minus previous critical index.
4Move prev and curr forward and increment index.
5If fewer than two critical points were found, return [-1, -1]. Otherwise return [minDistance, lastCritical - firstCritical].

Example Walkthrough

Input: head = [3, 1]

1.Only one interior node (value 1) with neighbors 3 and null on the right, so it is not a critical point.
2.No second critical point exists.

Output: [-1, -1]

Common Pitfalls

•The last node can never be critical because it has no right neighbor. Stop when curr.next is null.
•Use strict comparisons. Equal neighbors do not form a peak or valley.
•Indices are 1-based in the problem statement. Start counting from the head as index 1.
•maxDistance uses the first and last critical indices, not the minimum gap pair.

2058.cs

// Approach: Walk the list once. A critical point is a local peak or valley. Track
// the first index, the previous critical index, and the min gap between
// consecutive critical points. Max distance is last minus first.
// Complexity: O(n) time and O(1) extra space.

public class ListNode
{
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null)
    {
        this.val = val;
        this.next = next;
    }
}

public class Solution
{
    public int[] NodesBetweenCriticalPoints(ListNode head)
    {
        int minDistance = Int32.MaxValue;
        int firstMaIndex = -1, prevMaIndex = -1, index = 1;
        ListNode prev = head;
        ListNode curr = head.next;

        while (curr.next != null)
        {
            if (curr.val > prev.val && curr.val > curr.next.val ||
                curr.val < prev.val && curr.val < curr.next.val)
            {
                if (firstMaIndex == -1)
                    firstMaIndex = index;
                if (prevMaIndex != -1)
                    minDistance = Math.Min(minDistance, index - prevMaIndex);
                prevMaIndex = index;
            }
            prev = curr;
            curr = curr.next;
            index++;
        }

        if (minDistance == Int32.MaxValue)
            return new int[] { -1, -1 };

        return new int[] { minDistance, prevMaIndex - firstMaIndex };
    }
}

Was this solution helpful?