⚡Flashcard Drill➔
NeetCode #317LC-2058MediumLinked List
← Back to All Problems

#317 · #2058 · Find the Minimum and Maximum Number of Nodes Between Critical Points(找出临界点之间的最小和最大距离)

📌 Problem Statement & Constraints

A critical point in a linked list is either a local minimum or a local maximum. Given the head of a linked list, return [minDistance, maxDistance] where the distances are between pairs of critical points; if there are fewer than two, return [-1, -1]. Constraints: the number of nodes is in [2, 10^5], 1 <= Node.val <= 10^5.

💡 Core Algorithmic Approaches

  1. Walk three consecutive nodes at a time and test whether the middle one is a local extremum.
  2. Collect the indices of all critical points.
  3. The maximum distance is from the first to the last; the minimum is the smallest gap between consecutive critical points.
  4. Returning [-1, -1] when fewer than two critical points exist.

💻 Benchmark Python3 Implementation

class Solution:
    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
        if not head or not head.next or not head.next.next:
            return [-1, -1]
        idx = []
        i = 1                              # index of the middle node (head is 0)
        prev, cur, nxt = head, head.next, head.next.next
        while nxt:
            if (cur.val > prev.val and cur.val > nxt.val) or \
               (cur.val < prev.val and cur.val < nxt.val):
                idx.append(i)              # local extremum
            prev, cur, nxt = cur, nxt, nxt.next
            i += 1
        if len(idx) < 2:
            return [-1, -1]
        min_dist = min(idx[k] - idx[k - 1] for k in range(1, len(idx)))
        max_dist = idx[-1] - idx[0]
        return [min_dist, max_dist]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass over the list.
💾 Space Complexity
O(k) for the critical-point indices, where k is their count (O(1) if the minimum and maximum are tracked on the fly).

⚠️ Interview Pitfalls & Follow-ups

  • Testing only the middle against one neighbour: a critical point must be strictly greater than both neighbours or strictly less than both.
  • Using >= in the comparisons: equality disqualifies the node from being a critical point.
  • Computing the maximum distance as the largest consecutive gap: the maximum is first-to-last, which the sorted index list gives directly.
  • Forgetting the fewer-than-two case: return [-1, -1].
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems