Find the Minimum and Maximum Number of Nodes Between Critical Points

Find the Minimum and Maximum Number of Nodes Between Critical Points - Problem

Linked List Medium

A critical point in a linked list is defined as either a local maxima or a local minima.

A node is a local maxima if the current node has a value strictly greater than the previous node and the next node.

A node is a local minima if the current node has a value strictly smaller than the previous node and the next node.

Note that a node can only be a local maxima/minima if there exists both a previous node and a next node.

Given a linked list head, return an array of length 2 containing [minDistance, maxDistance] where minDistance is the minimum distance between any two distinct critical points and maxDistance is the maximum distance between any two distinct critical points. If there are fewer than two critical points, return [-1, -1].

Input & Output

Example 1 — Basic Case with Multiple Critical Points

$ Input: head = [3,1]

› Output: [-1,-1]

💡 Note: There are no critical points in [3,1] since we need at least 3 nodes to have a node with both previous and next nodes.

Example 2 — Sufficient Critical Points

$ Input: head = [5,3,1,2,5,1,2]

› Output: [1,3]

💡 Note: Critical points are at indices 1 (local maxima: 3>5 and 3>1), 2 (local minima: 1<3 and 1<2), and 5 (local minima: 1<5 and 1<2). Min distance is 1 (between indices 1 and 2), max distance is 4 (between indices 1 and 5).

Example 3 — Only Two Critical Points

$ Input: head = [1,3,2,2,3,2,2,2,7]

› Output: [3,3]

💡 Note: Critical points are at indices 1 (local maxima: 3>1 and 3>2) and 4 (local maxima: 3>2 and 3>2). Distance between them is 3, so both min and max distances are 3.

Constraints

The number of nodes in the list is in the range [2, 10⁵]
1 ≤ Node.val ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Linked list with values: [5,3,1,2,5,1,2]

Find Critical Points

Identify positions where value is local max/min compared to neighbors

Calculate Distances

Find minimum and maximum distances between critical points

Key Takeaway

🎯 Key Insight: Track first and previous critical point positions to calculate min/max distances in one pass

Asked in

a Amazon 15 M Microsoft 12 G Google 8

The key insight is to identify critical points (local maxima/minima) while traversing and track distances efficiently. The optimal approach uses a single pass to find critical points and calculate min/max distances simultaneously. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Store All Critical Points	O(n + k²)	O(k)	Find all critical points first, then calculate all pairwise distances
Optimized - Single Pass	O(n)	O(1)	Calculate minimum and maximum distances in one traversal

Brute Force - Store All Critical Points — Algorithm Steps

Step 1: Traverse the linked list and store positions of all critical points
Step 2: Calculate distances between every pair of critical points
Step 3: Return the minimum and maximum distances found

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Critical Points

Traverse list and identify local maxima/minima

Store Positions

Keep array of critical point positions

Calculate Distances

Compare all pairs to find min/max distances

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

int* solution(struct ListNode* head, int* returnSize) {
    *returnSize = 2;
    int* result = (int*)malloc(2 * sizeof(int));
    
    if (!head || !head->next || !head->next->next) {
        result[0] = -1;
        result[1] = -1;
        return result;
    }
    
    int criticalPoints[100000];
    int count = 0;
    
    struct ListNode* prev = head;
    struct ListNode* curr = head->next;
    int position = 1;
    
    while (curr->next) {
        if ((curr->val > prev->val && curr->val > curr->next->val) || 
            (curr->val < prev->val && curr->val < curr->next->val)) {
            criticalPoints[count++] = position;
        }
        
        prev = curr;
        curr = curr->next;
        position++;
    }
    
    if (count < 2) {
        result[0] = -1;
        result[1] = -1;
        return result;
    }
    
    int minDistance = INT_MAX;
    int maxDistance = 0;
    
    for (int i = 0; i < count; i++) {
        for (int j = i + 1; j < count; j++) {
            int distance = criticalPoints[j] - criticalPoints[i];
            if (distance < minDistance) minDistance = distance;
            if (distance > maxDistance) maxDistance = distance;
        }
    }
    
    result[0] = minDistance;
    result[1] = maxDistance;
    return result;
}

struct ListNode* buildList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;
    
    struct ListNode* curr = head;
    for (int i = 1; i < size; i++) {
        curr->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        curr->next->val = arr[i];
        curr->next->next = NULL;
        curr = curr->next;
    }
    return head;
}

int main() {
    char line[1000000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int arr[100000];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        arr[size++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    struct ListNode* head = buildList(arr, size);
    int returnSize;
    int* result = solution(head, &returnSize);
    
    printf("[%d,%d]\n", result[0], result[1]);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + k²)

O(n) to find critical points, O(k²) to compare all pairs where k is number of critical points

✓ Linear Growth

Space Complexity

O(k)

Array to store positions of k critical points

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Store All Critical Points — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler