2058. Find the Minimum and Maximum Number of Nodes Between Critical Points
Tags: php, leetcode, algorithms, programming
Published: 2024-07-05 17:09:40

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

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]`_.

**Example 1:**

![a1](https://assets.leetcode.com/uploads/2021/10/13/a1.png)

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

**Example 2:**

![a2](https://assets.leetcode.com/uploads/2021/10/13/a2.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:**

![a5](https://assets.leetcode.com/uploads/2021/10/14/a5.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 <code>[2, 10<sup>5</sup>]</code>.
 - <code>1 <= Node.val <= 10<sup>5</sup></code>


**Solution:**

```
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {

    /**
     * @param ListNode $head
     * @return Integer[]
     */
    function nodesBetweenCriticalPoints($head) {
        $result = [-1, -1];

        // Initialize minimum distance to the maximum possible value
        $minDistance = PHP_INT_MAX;

        // Pointers to track the previous node, current node, and indices
        $previousNode = $head;
        $currentNode = $head->next;
        $currentIndex = 1;
        $previousCriticalIndex = 0;
        $firstCriticalIndex = 0;

        while ($currentNode->next != null) {
            // Check if the current node is a local maxima or minima
            if (($currentNode->val < $previousNode->val &&
                    $currentNode->val < $currentNode->next->val) ||
                ($currentNode->val > $previousNode->val &&
                    $currentNode->val > $currentNode->next->val)) {
                // If this is the first critical point found
                if ($previousCriticalIndex == 0) {
                    $previousCriticalIndex = $currentIndex;
                    $firstCriticalIndex = $currentIndex;
                } else {
                    // Calculate the minimum distance between critical points
                    $minDistance = min($minDistance, $currentIndex - $previousCriticalIndex);
                    $previousCriticalIndex = $currentIndex;
                }
            }

            // Move to the next node and update indices
            $currentIndex++;
            $previousNode = $currentNode;
            $currentNode = $currentNode->next;
        }

        // If at least two critical points were found
        if ($minDistance != PHP_INT_MAX) {
            $maxDistance = $previousCriticalIndex - $firstCriticalIndex;
            $result = [$minDistance, $maxDistance];
        }

        return $result;
    }
}
```

- **[LinkedIn](https://www.linkedin.com/in/arifulhaque/)**
- **[GitHub](https://github.com/mah-shamim)**