Find the Minimum and Maximum Number of Nodes Between Critical Points
MediumLinked List
Solution
import { ListNode } from '@algorithm/lib';
export function nodesBetweenCriticalPoints(head: ListNode | null): number[] {
if (head === null) {
return [-1, -1];
}
let [start, end] = [Number.MAX_SAFE_INTEGER, 0];
let minDistance = Number.MAX_SAFE_INTEGER;
let prevNode: ListNode | null = null;
let currentNode: ListNode | null = head;
let currentIndex = 0;
while (currentNode !== null) {
if (isCriticalPoint(prevNode, currentNode)) {
if (end !== 0) {
minDistance = Math.min(minDistance, currentIndex - end);
}
start = Math.min(start, currentIndex);
end = currentIndex;
}
prevNode = currentNode;
currentNode = currentNode.next;
currentIndex += 1;
}
if (minDistance === Number.MAX_SAFE_INTEGER) {
return [-1, -1];
}
return [minDistance, end - start];
}
function isCriticalPoint(prevNode: ListNode | null, currentNode: ListNode | null) {
if (!prevNode || !currentNode || !currentNode.next) {
return false;
}
return (
Math.max(prevNode.val, currentNode.next.val) < currentNode.val ||
Math.min(prevNode.val, currentNode.next.val) > currentNode.val
);
}
Complexity
- Time:
O(N)
- Space:
O(1)