2058. Find the Minimum and Maximum Number of Nodes Between Critical Points

MediumLinked List
Leetcode Link

Problem Description

In this problem, we're dealing with a linked list where we need to find critical points - which are defined as either a local maxima or a local minima. A local maxima is considered as a node that has a value strictly greater than the nodes before and after it. Similarly, a local minima is a node that has a value strictly smaller than the nodes before and after it. However, a node can only be considered a critical point if it isn’t the first or last node, meaning it has both a previous and a next node.

Your task is to calculate the minimum and maximum distance between any two critical points in the linked list. The distance is calculated based on the positions of the nodes, not their values. If there are less than two critical points, the answer will be [-1, -1].

Intuition

To solve this problem, we need to traverse through the linked list to find the critical points and calculate the minimum and maximum distances between them.

  1. We initiate a traversal starting with the second node in the list since the first node can't be a critical point by the problem's definition.

  2. As we traverse, we compare the value of the current node with the values of its previous and next nodes to determine if it's a local maxima or minima.

  3. When we identify a critical point, we calculate the distance from the last found critical point. If it’s the first critical point found, we simply mark it as first and last; otherwise, we update the minimum distance every time we find a new critical point, and we set the maximum distance as the difference between the first critical point found and the current one, since this is likely to be the maximum distance as we traverse the list.

  4. To keep track of the index of nodes, we use a counter that increments with each traversal step.

  5. We utilize a pair of variables [minDistance, maxDistance] initialized to [inf, -inf] to keep track of the distances. These will be updated accordingly as we identify critical points.

  6. At the end of traversal, we check whether we have found at least two critical points. If we have only found one or none, we return [-1, -1]. Otherwise, we return the distances found.

By following this approach, we ensure that we only pass through the list once (O(n) time complexity), and use O(1) auxiliary space, ensuring an efficient solution.

Learn more about Linked List patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Depth first search is equivalent to which of the tree traversal order?

Solution Approach

The Solution Approach to finding the critical points in a linked list involves a single pass algorithm and judicious use of pointers and variables to keep track of the critical points and their distances.

  1. Algorithm: We start by initializing our pointers, prev and curr, to the first and second nodes of the list respectively, because a critical point requires both a previous and next node; therefore, the first node cannot be one.

  2. Tracking First and Last Critical Point: We declare variables first and last to remember the positions of the first and last critical points found. They are initially set to None.

  3. Initializing the Answer: We prepare an array ans with two elements [inf, -inf] representing the minimum and maximum distances respectively. inf is a placeholder indicating that no minimum distance has been found yet, and -inf indicating that no maximum distance has been found yet.

  4. Traversing the List: We iterate through the linked list with a while loop that continues as long as the current node has a next node.

  5. Identifying Critical Points:

    • In each iteration, we check if curr.val (the value of the current node) is a local maximum or minimum compared to prev.val and curr.next.val.
    • This is done by checking if curr.val is strictly greater than both prev.val and curr.next.val for a local maximum or strictly smaller for a local minimum.

  6. Updating Distances: If a critical point is found:

    • If it’s the first critical point, we initialize both first and last to the current index i.
    • If it's not the first, we:
      • Calculate the distance from the last critical point by subtracting last from the current index i and update ans[0] with the minimum distance found so far.
      • Update ans[1] with the distance between the first critical point and the current one to maintain the maximum distance.
      • Then last is updated to the current index as the last seen critical point.

  7. Incrementing Index and Updating Pointers: After checking for a critical point, we increment our index i and move our pointers ahead to the next elements (prev and curr) to continue our traversal.

  8. Returning the Result: Once we finish traversing the list:

    • If first and last are the same, it means that either no critical points were found or there was only one critical point. In that case, we return [-1, -1].
    • Otherwise, we return the distances stored in ans, which contain the minimum and maximum distances between critical points.

By applying this step-by-step approach, we efficiently calculate the required distances with straight forward logic and optimal time and space complexity.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these pictures shows the visit order of a depth-first search?

Example Walkthrough

Consider the following linked list as an example:

1List: 1 -> 3 -> 2 -> 5 -> 3 -> 4

Following our solution approach:

  1. We initialize prev to node with value 1 and curr to node with value 3, with an index i starting at 1.

  2. Our variables first and last are initialized to None. The array ans is set to [inf, -inf].

  3. As we traverse the list, we reach the second node with value 3, it isn’t a critical point because it isn't smaller or larger than both neighbours.

  4. Move to the third node with value 2, this is a local minima since 2 is less than both 3 and 5. This is the first critical point, so we set both first and last to the current index i = 2. Since there’s no previous critical point to compare with, we proceed without updating ans.

  5. The next node, with value 5, is a local maxima as it is greater than 2 and 3. We find the distance to the last critical point (distance = 3 - 2 = 1), and update the ans array with the minimum distance thus far, ans[0] = min(inf, 1) = 1. We then set last to 3 since 5 is now the last critical point we've seen.

  6. Moving forward, node 3 is not a critical point because it isn't a local minima or maxima.

  7. Finally, the node with value 4 is a local maxima. We update the minimum distance if it's smaller than the current ans[0] value (it's not in this case: 1 < 2 is false), and then, we update the ans[1] with the maximum distance found which is from the first critical point to the current one (distance = 5 - 2 = 3). We also update last to the current index i = 5.

  8. The traversal ends, and since first != last, we have found at least two critical points.

  9. We conclude the minimum distance between critical points is 1 and the maximum is 3, hence we return [1, 3].

Here's the example summarized in the required markdown template:

1
2Let's consider a linked list with the following sequence of nodes:
3

1 -> 3 -> 2 -> 5 -> 3 -> 4

1
2We'll walk through the solution approach step by step.
3
4- We start at the second node (`3`) since the first node can’t be a critical point.
5- The second node (`3`) isn’t a local maxima or minima, so we move to the next node.
6- At the third node (`2`), we identify our first critical point, it's a local minima.
7- Then we come across the fourth node (`5`) which is a local maxima. We find that the minimum distance to the previous critical point is `1`.
8- The fifth node (`3`) isn't a critical point, so we continue.
9- Lastly, at the sixth node (`4`), we've got another local maxima. We now know the maximum distance is `3`, between the third node and this one.
10
11After walking through the entire linked list, we determine the minimum distance between critical points is `1` and the maximum distance is `3`, which gives us our final answer: `[1, 3]`.

Solution Implementation

1from typing import Optional, List
2from math import inf
3
4class ListNode:
5    # Definition for a singly-linked list node
6    def __init__(self, val=0, next_node=None):
7        self.val = val
8        self.next = next_node
9
10class Solution:
11    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
12        # Initialize markers for previous and current nodes
13        prev_node, curr_node = head, head.next
14      
15        # Initialize the first and last positions of critical points to None
16        first_critical, last_critical = None, None
17      
18        index = 1  # Start from index 1 since we are checking from the second node
19        min_distance, max_distance = inf, -inf  # Set initial distances
20      
21        # Iterate through the linked list to find critical points
22        while curr_node.next:
23            # Check if the current node is a critical point (local min or local max)
24            if curr_node.val < min(prev_node.val, curr_node.next.val) or \
25               curr_node.val > max(prev_node.val, curr_node.next.val):
26                # If it is the first critical point encountered, set both first and last
27                if last_critical is None:
28                    first_critical = last_critical = index
29                else:
30                    # Update the minimum distance if the current critical point
31                    # is closer to the previous critical point than other pairs
32                    min_distance = min(min_distance, index - last_critical)
33                    # Update the maximum distance from the current to the first critical point
34                    max_distance = index - first_critical
35                    # Update the last critical point to the current index
36                    last_critical = index
37            # Move to the next index
38            index += 1
39            # Update prev_node and curr_node to step through the list
40            prev_node, curr_node = curr_node, curr_node.next
41      
42        # If no critical points or only one critical point found, return [-1, -1]
43        # else, return the found minimum and maximum distances
44        return [min_distance, max_distance] if first_critical != last_critical else [-1, -1]
45
1class Solution {
2    public int[] nodesBetweenCriticalPoints(ListNode head) {
3        // Initialize pointers and set the index for iteration
4        ListNode previousNode = head;
5        ListNode currentNode = head.next;
6        int firstCriticalIndex = 0, lastCriticalIndex = 0;
7        int index = 1;
8      
9        // Initialize the answer array with maximum and minimum values respectively
10        int[] answer = new int[] {Integer.MAX_VALUE, Integer.MIN_VALUE};
11      
12        // Iterate through the list until we reach the end
13        while (currentNode.next != null) {
14            // Check if the current node is a critical point (local minimum or maximum)
15            if (currentNode.val < Math.min(previousNode.val, currentNode.next.val)
16                    || currentNode.val > Math.max(previousNode.val, currentNode.next.val)) {
17                // Update the first and last critical points found
18                if (lastCriticalIndex == 0) {
19                    // This means we found the first critical point
20                    firstCriticalIndex = index;
21                    lastCriticalIndex = index;
22                } else {
23                    // Update the minimum distance between critical points
24                    answer[0] = Math.min(answer[0], index - lastCriticalIndex);
25                    // Update the maximum distance from the first to the current critical point
26                    answer[1] = index - firstCriticalIndex;
27                    // Update the last critical point found
28                    lastCriticalIndex = index;
29                }
30            }
31            // Move to the next node in the list
32            ++index;
33            previousNode = currentNode;
34            currentNode = currentNode.next;
35        }
36      
37        // If only one critical point was found, then return [-1, -1]
38        // Otherwise, return the array containing minimum and maximum distances
39        return firstCriticalIndex == lastCriticalIndex ? new int[] {-1, -1} : answer;
40    }
41}
42
43/**
44 * Definition for singly-linked list.
45 */
46class ListNode {
47    int val;
48    ListNode next;
49  
50    ListNode() {}
51  
52    ListNode(int val) {
53        this.val = val;
54    }
55  
56    ListNode(int val, ListNode next) {
57        this.val = val;
58        this.next = next;
59    }
60}
61
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11
12class Solution {
13public:
14    vector<int> nodesBetweenCriticalPoints(ListNode* head) {
15        // Pointers to track the current and previous nodes in the list
16        ListNode* previous = head;
17        ListNode* current = head->next;
18
19        // Variables to keep track of the positions of the first and last critical points
20        int firstCriticalPosition = 0, lastCriticalPosition = 0;
21        int index = 1; // Current index within the linked list
22
23        // Initialize the answer with the maximum value for distance calculations
24        vector<int> answer(2, INT_MAX);
25      
26        // Iterate through the linked list to find critical points
27        while (current->next) {
28            // Check for a critical point, which is either a local minimum or maximum
29            bool isCritical = current->val < min(previous->val, current->next->val) || 
30                              current->val > max(previous->val, current->next->val);
31
32            if (isCritical) {
33                if (lastCriticalPosition == 0) {
34                    // This is the first critical point encountered
35                    firstCriticalPosition = index;
36                } else {
37                    // Update the shortest distance between any two critical points
38                    answer[0] = min(answer[0], index - lastCriticalPosition);
39                    // Update the distance between the first and the current critical point
40                    answer[1] = index - firstCriticalPosition;
41                }
42                // Update the position of the last critical point 
43                lastCriticalPosition = index;
44            }
45            ++index; // Move to the next index
46            previous = current; // Move the previous pointer forward
47            current = current->next; // Move the current pointer forward
48        }
49        // If no critical points or only one critical point was found, return {-1, -1}
50        if (firstCriticalPosition == lastCriticalPosition) {
51            return {-1, -1};
52        }
53        // Return the distances between critical points
54        return answer;
55    }
56};
57
1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5    val: number;
6    next: ListNode | null;
7    constructor(val?: number, next?: ListNode | null) {
8        this.val = (val === undefined ? 0 : val);
9        this.next = (next === undefined ? null : next);
10    }
11}
12
13/**
14 * Finds the minimum and maximum distance between any two critical points in a linked list.
15 * Critical points are defined as local minima or local maxima.
16 * If fewer than two critical points are found, returns [-1, -1].
17 * @param {ListNode | null} head - The head node of the linked list.
18 * @return {number[]} - An array with two elements: the minimum and maximum distances between critical points.
19 */
20function nodesBetweenCriticalPoints(head: ListNode | null): number[] {
21    let index = 1; // Stores the current node index.
22    let previousValue = head.val; // Stores the value of the previous node.
23    head = head.next; // Move head to the next node.
24    let criticalPoints = []; // Stores the indices of the critical points.
25
26    // Traverse the list to find all critical points.
27    while (head && head.next !== null) {
28        let currentValue = head.val;
29        let postValue = head.next.val;
30        // Check if the current node is a local maximum or minimum.
31        if ((previousValue < currentValue && currentValue > postValue) ||
32            (previousValue > currentValue && currentValue < postValue)) {
33            criticalPoints.push(index);
34        }
35        previousValue = currentValue;
36        index++;
37        head = head.next;
38    }
39
40    // Determine the number of critical points.
41    let numCriticalPoints = criticalPoints.length;
42    // If there are less than two critical points, return [-1, -1].
43    if (numCriticalPoints < 2) return [-1, -1];
44
45    let minDistance = Infinity; // Initialize the minimum distance to infinity.
46    // Calculate the minimum distance between consecutive critical points.
47    for (let i = 1; i < numCriticalPoints; i++) {
48        minDistance = Math.min(criticalPoints[i] - criticalPoints[i - 1], minDistance);
49    }
50  
51    // Calculate the maximum distance, which is distance between the first and the last critical points.
52    let maxDistance = criticalPoints[numCriticalPoints - 1] - criticalPoints[0];
53
54    // Return the minimum and maximum distances as an array.
55    return [minDistance, maxDistance];
56}
57
Not Sure What to Study? Take the 2-min Quiz：

What data structure does Breadth-first search typically uses to store intermediate states?

Time and Space Complexity

The time complexity of the given code is O(n), where n is the number of nodes in the linked list. The algorithm iterates through the list once with a single pass, checking each node to determine if it's a critical point—either a local minimum or a local maximum. The checks for minimum and maximum at each step are constant-time operations.

The space complexity of the code is O(1). The space used by the algorithm does not scale with the input size as it only maintains a constant number of pointers and variables (prev, curr, first, last, i, and ans) regardless of the length of the list.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search is equivalent to which of the tree traversal order?

Recommended Readings

Linked List Cycle

Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫