Find the Minimum and Maximum Number of Nodes Between Critical Points

Medium
2018.

Find the Minimum and Maximum Number of Nodes Between Critical Points

MediumLinked ListSimulationAmazon

Find the Minimum and Maximum Number of Nodes Between Critical Points is a medium coding problem on simulation, asked in Amazon interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {number[]}
 */
var nodesBetweenCriticalPoints = function(head) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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

  1. Hint 1

    Walk the list with a window of three consecutive values to decide whether the middle node is critical.

  2. Hint 2

    The maximum distance is always between the first and the last critical point.

  3. 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

  1. Set first = last = -1, minGap = ∞, and walk with prev (value before), cur (current node) and its index i, starting at the second node.
  2. If cur.next exists and cur.val is strictly above or strictly below both prev and cur.next.val, it is critical: if last != -1, set minGap = min(minGap, i - last); if first == -1, set first = i; set last = i.
  3. Advance prev, cur and i.
  4. 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.

All 137 simulation problems · the whole catalogue