Find the Minimum and Maximum Number of Nodes Between Critical Points
Find the Minimum and Maximum Number of Nodes Between Critical Points solution: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Find the Minimum and Maximum Number of Nodes Between Critical Points is a medium coding problem on simulation, asked in Amazon interviews.
- Difficulty: Medium
- Topics: Simulation
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A critical point of a linked list is a node that is either a local maximum (its value is strictly greater than both its previous and next nodes' values) or a local minimum (strictly smaller than both). A node is only critical if it has both a previous and a next node.
Given the head of a linked list, return [minDistance, maxDistance], where minDistance is the smallest and maxDistance the largest distance (difference of positions) between any two distinct critical points. If there are fewer than two critical points, return [-1, -1].
Example 1
Input: head = [3,1]
Output: [-1,-1]
Explanation: There are no critical points.
Example 2
Input: head = [5,3,1,2,5,1,2]
Output: [1,3]
Explanation: Critical points are at positions 2 (value 1, a minimum), 4 (value 5, a maximum) and 5 (value 1, a minimum), counting from 0. The closest pair is 4 and 5; the farthest is 2 and 5.
Example 3
Input: head = [1,3,2,2,3,2,2,2,7]
Output: [3,3]
Explanation: Only positions 1 and 4 are critical; equal neighbours never make a point critical.
Constraints
The number of nodes in the list is in the range [2, 10^5]1 <= Node.val <= 10^5
Hints for Find the Minimum and Maximum Number of Nodes Between Critical Points
Hint 1
Walk the list with a window of three consecutive values to decide whether the middle node is critical.
Hint 2
The maximum distance is always between the first and the last critical point.
Hint 3
The minimum distance is always between two consecutive critical points, so remember the previous critical position and update the minimum gap as you go.
How to solve Find the Minimum and Maximum Number of Nodes Between Critical Points
One pass with three consecutive values identifies every critical point in order. The farthest pair is the first and last of them, and the closest pair must be two neighbours in that order, so only the first, the previous and the current critical positions need to be kept.
Approach
- Set
first = last = -1,minGap = ∞, and walk withprev(value before),cur(current node) and its indexi, starting at the second node. - If
cur.nextexists andcur.valis strictly above or strictly below bothprevandcur.next.val, it is critical: iflast != -1, setminGap = min(minGap, i - last); iffirst == -1, setfirst = i; setlast = i. - Advance
prev,curandi. - If
first == last(zero or one critical point), return[-1, -1]; otherwise return[minGap, last - first].
Why it works
Critical points are discovered in increasing position. For any two non-adjacent critical points in that order there is one between them, which is closer to each — so the minimum is attained by consecutive ones. The maximum difference of an increasing sequence is last minus first.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The first and last nodes can never be critical.
- Use strict comparisons: a node equal to a neighbour is not a local extremum.
- Comparing every pair of critical points is O(k²) — unnecessary given the consecutive-pair argument.
Reference solution
Python
from typing import List, Optional
def nodesBetweenCriticalPoints(head: Optional[ListNode]) -> List[int]:
first = last = -1
min_gap = float("inf")
prev, cur, i = head.val, head.next, 1
while cur.next:
nxt = cur.next.val
if (cur.val > prev and cur.val > nxt) or (cur.val < prev and cur.val < nxt):
if last != -1:
min_gap = min(min_gap, i - last)
if first == -1:
first = i
last = i
prev, cur, i = cur.val, cur.next, i + 1
if first == last:
return [-1, -1]
return [min_gap, last - first]Java
public static int[] nodesBetweenCriticalPoints(ListNode head) {
int first = -1, last = -1, minGap = Integer.MAX_VALUE;
int prev = head.val, i = 1;
ListNode cur = head.next;
while (cur.next != null) {
int nxt = cur.next.val;
if ((cur.val > prev && cur.val > nxt) || (cur.val < prev && cur.val < nxt)) {
if (last != -1) minGap = Math.min(minGap, i - last);
if (first == -1) first = i;
last = i;
}
prev = cur.val;
cur = cur.next;
i++;
}
return first == last ? new int[] { -1, -1 } : new int[] { minGap, last - first };
}C++
vector<int> nodesBetweenCriticalPoints(ListNode* head) {
int first = -1, last = -1, minGap = INT_MAX;
int prev = head->val, i = 1;
ListNode* cur = head->next;
while (cur->next) {
int nxt = cur->next->val;
if ((cur->val > prev && cur->val > nxt) || (cur->val < prev && cur->val < nxt)) {
if (last != -1) minGap = min(minGap, i - last);
if (first == -1) first = i;
last = i;
}
prev = cur->val;
cur = cur->next;
i++;
}
if (first == last) return { -1, -1 };
return { minGap, last - first };
}JavaScript
var nodesBetweenCriticalPoints = function(head) {
var first = -1, last = -1, minGap = Infinity;
var prev = head.val, cur = head.next, i = 1;
while (cur.next !== null) {
var nxt = cur.next.val;
if ((cur.val > prev && cur.val > nxt) || (cur.val < prev && cur.val < nxt)) {
if (last !== -1) minGap = Math.min(minGap, i - last);
if (first === -1) first = i;
last = i;
}
prev = cur.val;
cur = cur.next;
i++;
}
return first === last ? [-1, -1] : [minGap, last - first];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.