# Find the Minimum and Maximum Number of Nodes Between Critical Points
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-minimum-and-maximum-number-of-nodes-between-critical-points)
Canonical: https://scaleengineer.com/dsa/problems/find-the-minimum-and-maximum-number-of-nodes-between-critical-points
**Data structures:** Linked List
**Companies:** [josh technology](https://scaleengineer.com/companies/josh-technology), [Info Edge](https://scaleengineer.com/companies/info-edge)
---
## Problem
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]`.

**Example 1:**

![](https://assets.glich.co/dsa/find-the-minimum-and-maximum-number-of-nodes-between-critical-points/image0.png) 

**Input:** head = [3,1]
**Output:** [-1,-1]
**Explanation:** There are no critical points in [3,1].

**Example 2:**

![](https://assets.glich.co/dsa/find-the-minimum-and-maximum-number-of-nodes-between-critical-points/image1.png) 

**Input:** head = [5,3,1,2,5,1,2]
**Output:** [1,3]
**Explanation:** There are three critical points:
- [5,3,**1**,2,5,1,2]: The third node is a local minima because 1 is less than 3 and 2.
- [5,3,1,2,**5**,1,2]: The fifth node is a local maxima because 5 is greater than 2 and 1.
- [5,3,1,2,5,**1**,2]: The sixth node is a local minima because 1 is less than 5 and 2.
The minimum distance is between the fifth and the sixth node. minDistance = 6 - 5 = 1.
The maximum distance is between the third and the sixth node. maxDistance = 6 - 3 = 3.

**Example 3:**

![](https://assets.glich.co/dsa/find-the-minimum-and-maximum-number-of-nodes-between-critical-points/image2.png) 

**Input:** head = [1,3,2,2,3,2,2,2,7]
**Output:** [3,3]
**Explanation:** There are two critical points:
- [1,**3**,2,2,3,2,2,2,7]: The second node is a local maxima because 3 is greater than 1 and 2.
- [1,3,2,2,**3**,2,2,2,7]: The fifth node is a local maxima because 3 is greater than 2 and 2.
Both the minimum and maximum distances are between the second and the fifth node.
Thus, minDistance and maxDistance is 5 - 2 = 3.
Note that the last node is not considered a local maxima because it does not have a next node.

**Constraints:**

* The number of nodes in the list is in the range `[2, 105]`.
* `1 <= Node.val <= 105`

# Approaches
## Two-Pass Approach using a List
This approach involves two main steps. First, we traverse the entire linked list to identify all critical points and store their indices in a separate list. In the second step, we process this list of indices to calculate the minimum and maximum distances.
**Time:** O(N), where N is the number of nodes in the linked list. The first pass to find critical points takes O(N) time. The second pass over the list of critical point indices takes O(K) time, where K is the number of critical points (K <= N). Thus, the total time complexity is O(N). · **Space:** O(K), where K is the number of critical points. In the worst-case scenario (e.g., an alternating sequence like 1, 5, 1, 5, ...), K can be proportional to N, leading to a space complexity of O(N).
**Pros:** The logic is straightforward and easy to understand as it separates the problem into two distinct phases: finding points and then calculating distances.
**Cons:** Uses O(K) extra space, where K is the number of critical points. In the worst case, this can be O(N).; Requires two passes over the data (one on the linked list, one on the list of indices), which is less efficient than a single-pass solution.
### Explanation
We begin by initializing an empty list, say `criticalIndices`, to store the 1-based indices of all critical points. We then iterate through the linked list, starting from the second node up to the second-to-last node, as a critical point must have both a predecessor and a successor. We use three pointers: `prev`, `curr`, and `next` to check the condition for a critical point. For each node `curr`, we check if its value is strictly greater than both `prev.val` and `next.val` (local maxima) or strictly smaller than both (local minima). If it is, we add its index to our `criticalIndices` list. After the traversal is complete, we check the size of `criticalIndices`. If it's less than 2, it's impossible to form a pair of distinct critical points, so we return `[-1, -1]`. Otherwise, the maximum distance is the difference between the last and the first index in the list. To find the minimum distance, we iterate through the `criticalIndices` list and find the minimum difference between any two adjacent indices. Finally, we return the calculated `[minDistance, maxDistance]`.

```java
import java.util.ArrayList;
import java.util.List;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int[] nodesBetweenCriticalPoints(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return new int[]{-1, -1};
        }

        List<Integer> criticalIndices = new ArrayList<>();
        ListNode prev = head;
        ListNode curr = head.next;
        int index = 2;

        while (curr.next != null) {
            ListNode next = curr.next;
            if ((curr.val > prev.val && curr.val > next.val) || 
                (curr.val < prev.val && curr.val < next.val)) {
                criticalIndices.add(index);
            }
            prev = curr;
            curr = next;
            index++;
        }

        if (criticalIndices.size() < 2) {
            return new int[]{-1, -1};
        }

        int minDistance = Integer.MAX_VALUE;
        for (int i = 1; i < criticalIndices.size(); i++) {
            minDistance = Math.min(minDistance, criticalIndices.get(i) - criticalIndices.get(i - 1));
        }

        int maxDistance = criticalIndices.get(criticalIndices.size() - 1) - criticalIndices.get(0);

        return new int[]{minDistance, maxDistance};
    }
}
```
### Algorithm
- Initialize an empty list `criticalIndices` to store the indices of critical points.
- Initialize three pointers, `prev = head`, `curr = head.next`, and an `index` counter starting at 2.
- Traverse the linked list from the second node until the second-to-last node (`while curr.next != null`).
- In each iteration, check if `curr` is a critical point by comparing its value with `prev.val` and `curr.next.val`.
  - A node is a local maxima if `curr.val > prev.val && curr.val > curr.next.val`.
  - A node is a local minima if `curr.val < prev.val && curr.val < curr.next.val`.
- If `curr` is a critical point, add its current `index` to the `criticalIndices` list.
- After the traversal, check if the size of `criticalIndices` is less than 2. If so, return `[-1, -1]`.
- Calculate the `maxDistance` as the difference between the last and first elements in `criticalIndices`.
- Calculate the `minDistance` by iterating through `criticalIndices` and finding the minimum difference between any two adjacent indices.
- Return `[minDistance, maxDistance]`.

## Single-Pass Constant-Space Approach
This optimized approach calculates the minimum and maximum distances in a single traversal of the linked list. By keeping track of the indices of the first and most recent critical points found, we can update the distances on the fly, thus avoiding the need for extra storage.
**Time:** O(N), where N is the number of nodes. We perform a single pass through the linked list. · **Space:** O(1). We only use a few variables to store state (`minDistance`, `firstCriticalIndex`, `prevCriticalIndex`, `index`), regardless of the size of the input list. This is a significant improvement over the two-pass approach.
**Pros:** Highly efficient in terms of memory, using only a constant amount of extra space.; Processes the list in a single pass, making it faster in practice by avoiding the overhead of intermediate data structures.
**Cons:** The logic can be slightly more complex to follow compared to the two-pass approach due to the need to manage multiple state variables (`firstCriticalIndex`, `prevCriticalIndex`) within a single loop.
### Explanation
We iterate through the linked list once, keeping track of the previous node, current node, and the current node's index. We also need a few variables: `firstCriticalIndex` to store the index of the very first critical point, `prevCriticalIndex` to store the index of the previously found critical point, and `minDistance` initialized to a very large value. The traversal starts from the second node. For each node, we check if it's a critical point (local maxima or minima). When we find a critical point at index `i`: if `firstCriticalIndex` has not been set yet, we set it to `i`. If `prevCriticalIndex` has been set (meaning we've found at least one critical point before this one), we can calculate the distance to the previous critical point: `i - prevCriticalIndex`. We then update `minDistance` with the minimum of its current value and this new distance. After processing, we always update `prevCriticalIndex` to the current index `i`, as it becomes the 'previous' critical point for the next one we find. After the loop finishes, if we have found fewer than two critical points (i.e., `minDistance` is still at its initial large value), we return `[-1, -1]`. Otherwise, the `maxDistance` is simply the difference between the last critical point we found (`prevCriticalIndex`) and the first one (`firstCriticalIndex`). We then return `[minDistance, maxDistance]`.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int[] nodesBetweenCriticalPoints(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return new int[]{-1, -1};
        }

        int minDistance = Integer.MAX_VALUE;
        int firstCriticalIndex = -1;
        int prevCriticalIndex = -1;

        ListNode prev = head;
        ListNode curr = head.next;
        int index = 2;

        while (curr.next != null) {
            ListNode next = curr.next;
            if ((curr.val > prev.val && curr.val > next.val) || 
                (curr.val < prev.val && curr.val < next.val)) {
                
                if (firstCriticalIndex == -1) {
                    firstCriticalIndex = index;
                }
                
                if (prevCriticalIndex != -1) {
                    minDistance = Math.min(minDistance, index - prevCriticalIndex);
                }
                
                prevCriticalIndex = index;
            }
            prev = curr;
            curr = next;
            index++;
        }

        if (minDistance == Integer.MAX_VALUE) {
            return new int[]{-1, -1};
        }

        int maxDistance = prevCriticalIndex - firstCriticalIndex;
        return new int[]{minDistance, maxDistance};
    }
}
```
### Algorithm
- Initialize `minDistance = Integer.MAX_VALUE`, `firstCriticalIndex = -1`, and `prevCriticalIndex = -1`.
- Initialize `prev = head`, `curr = head.next`, and `index = 2`.
- Iterate while `curr.next` is not null:
  - Let `next = curr.next`.
  - Check if `curr` is a critical point.
  - If it is:
    - If `firstCriticalIndex` is -1, set `firstCriticalIndex = index`.
    - If `prevCriticalIndex` is not -1, update `minDistance = min(minDistance, index - prevCriticalIndex)`.
    - Update `prevCriticalIndex = index`.
  - Update pointers: `prev = curr`, `curr = next`.
  - Increment `index`.
- After the loop, if `minDistance` is still `Integer.MAX_VALUE` (meaning fewer than two critical points were found), return `[-1, -1]`.
- Calculate `maxDistance = prevCriticalIndex - firstCriticalIndex`.
- Return `[minDistance, maxDistance]`.

# Solutions
### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public int [] nodesBetweenCriticalPoints ( ListNode head ) { ListNode prev = head ; ListNode curr = head . next ; int first = 0 , last = 0 ; int i = 1 ; int [] ans = new int [] { Integer . MAX_VALUE , Integer . MIN_VALUE }; while ( curr . next != null ) { if ( curr . val < Math . min ( prev . val , curr . next . val ) || curr . val > Math . max ( prev . val , curr . next . val )) { if ( last == 0 ) { first = i ; last = i ; } else { ans [ 0 ] = Math . min ( ans [ 0 ], i - last ); ans [ 1 ] = i - first ; last = i ; } } ++ i ; prev = curr ; curr = curr . next ; } return first == last ? new int [] {- 1 , - 1 } : ans ; } }
```

### CPP

```cpp
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: vector < int > nodesBetweenCriticalPoints ( ListNode * head ) { ListNode * prev = head ; ListNode * curr = head -> next ; int first = 0 , last = 0 ; int i = 1 ; vector < int > ans ( 2 , INT_MAX ); while ( curr -> next ) { if ( curr -> val < min ( prev -> val , curr -> next -> val ) || curr -> val > max ( prev -> val , curr -> next -> val )) { if ( last == 0 ) first = i ; else { ans [ 0 ] = min ( ans [ 0 ], i - last ); ans [ 1 ] = i - first ; } last = i ; } ++ i ; prev = curr ; curr = curr -> next ; } if ( first == last ) return { - 1 , - 1 }; return ans ; } };
```

### Python

```python
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def nodesBetweenCriticalPoints ( self , head : Optional [ ListNode ]) -> List [ int ]: prev , curr = head , head . next first = last = None i = 1 ans = [ inf , - inf ] while curr . next : if curr . val < min ( prev . val , curr . next . val ) or curr . val > max ( prev . val , curr . next . val ): if last is None : first = last = i else : ans [ 0 ] = min ( ans [ 0 ], i - last ) ans [ 1 ] = i - first last = i i += 1 prev , curr = curr , curr . next return ans if first != last else [ - 1 , - 1 ]
```