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
- Walk three consecutive nodes at a time and test whether the middle one is a local extremum.
- Collect the indices of all critical points.
- The maximum distance is from the first to the last; the minimum is the smallest gap between consecutive critical points.
- 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.