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,4]

💡 Note: Critical points are at indices 1 (local maxima: 3>5 and 3>1), 2 (local minima: 1<3 and 1<2), 4 (local maxima: 5>2 and 5>1), and 5 (local minima: 1<5 and 1<2). Min distance is 1 (between indices 1 and 2, or 4 and 5), 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

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

✓ Greedy

⏱️ Time: N/A Space: N/A

Brute Force - Store All Critical Points

⏱️ Time: O(n + k²) Space: O(k)

First traverse the linked list to collect all critical point positions in an array. Then calculate distances between every pair of critical points to find minimum and maximum distances.

Optimized - Single Pass

⏱️ Time: O(n) Space: O(1)

Traverse the linked list once, identifying critical points and calculating distances on the fly. Keep track of first critical point, previous critical point, and update min/max distances as we find new critical points.

Algorithm Steps — Algorithm Steps

Code -

solution.c — C

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

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

struct ListNode* createNode(int val) {
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

void solution(struct ListNode* head, int* result) {
    if (!head || !head->next || !head->next->next) {
        result[0] = -1;
        result[1] = -1;
        return;
    }
    
    struct ListNode* prev = head;
    struct ListNode* curr = head->next;
    int position = 1;
    
    int firstCritical = -1;
    int prevCritical = -1;
    int minDistance = INT_MAX;
    int maxDistance = 0;
    
    while (curr->next) {
        // Check if curr is a critical point
        if ((curr->val > prev->val && curr->val > curr->next->val) ||
            (curr->val < prev->val && curr->val < curr->next->val)) {
            if (firstCritical == -1) {
                firstCritical = position;
            } else {
                // Calculate distances
                if (prevCritical != -1) {
                    int dist = position - prevCritical;
                    if (dist < minDistance) {
                        minDistance = dist;
                    }
                }
                maxDistance = position - firstCritical;
            }
            prevCritical = position;
        }
        
        prev = curr;
        curr = curr->next;
        position++;
    }
    
    if (firstCritical == -1 || maxDistance == 0) {
        result[0] = -1;
        result[1] = -1;
    } else {
        result[0] = minDistance;
        result[1] = maxDistance;
    }
}

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

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int headArr[1000];
    int n = 0;
    
    if (strlen(line) > 3) {
        char* token = strtok(line + 1, ",]");
        while (token != NULL) {
            headArr[n++] = (int)strtol(token, NULL, 10);
            token = strtok(NULL, ",]");
        }
    }
    
    struct ListNode* head = buildList(headArr, n);
    int result[2];
    solution(head, result);
    
    printf("[%d,%d]\n", result[0], result[1]);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

✓ Linear Growth

Space Complexity

✓ 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