Find the Minimum and Maximum Number of Nodes Between Critical Points

Find the Minimum and Maximum Number of Nodes Between Critical Points

What is this problem about?

The Find the Minimum and Maximum Number of Nodes Between Critical Points interview question involves a linked list. A "critical point" is a node that is either a local maximum (strictly greater than both its predecessor and successor) or a local minimum (strictly smaller than both). You need to find the minimum and maximum distance between any two distinct critical points in the list.

Why is this asked in interviews?

Microsoft and Meta ask this to test your proficiency with Linked List interview patterns. It requires you to maintain a window of three nodes (previous, current, next) while traversing the list. It evaluations your ability to handle edge cases, such as lists with fewer than two critical points, and your skill in tracking positions to calculate distances on the fly.

Algorithmic pattern used

This is a Linked List Traversal with Position Tracking.

1. Iterate through the list starting from the second node.
2. Maintain a prev node pointer and look at curr.next.
3. Check if curr is a critical point by comparing prev.val, curr.val, and curr.next.val.
4. Keep track of the firstCriticalIndex, lastCriticalIndex, and minDistance.
5. For each new critical point found:
   • Update minDistance = min(minDistance, currentIndex - lastCriticalIndex).
   • Update lastCriticalIndex = currentIndex.
   • If it's the first one, set firstCriticalIndex.
6. The maxDistance is simply lastCriticalIndex - firstCriticalIndex.

Example explanation

List: 3 -> 1 -> 3 -> 3 -> 2 -> 2 -> 1

1. Indices: 0, 1, 2, 3, 4, 5, 6.
2. Index 1 (val 1): $1 < 3$ and $1 < 3$. Local Minimum! first = 1, last = 1.
3. Index 2 (val 3): Not strictly greater than 3.
4. Index 4 (val 2): Not strictly greater or smaller. ... continue. If you had another critical point at index 5, the min distance would be $5-1=4$.

Common mistakes candidates make

• Ignoring "Strictly": Counting a node as a critical point if it's equal to its neighbor.
• Fewer than two points: Failing to return [-1, -1] if only one (or zero) critical point exists.
• Memory Overhead: Trying to convert the linked list into an array first, which uses $O(N)$ extra space when the problem can be solved in $O(1)$ space.

Interview preparation tip

For linked list problems that involve neighbors, use a prev pointer and always check if curr.next exists before entering the loop logic. This "Three-Node Window" is a standard technique for identifying local properties in sequences.