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

In this guide, you will get 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points LeetCode Solution with the best time and space complexity. The solution to Find the Minimum and Maximum Number of Nodes Between Critical Points problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Find the Minimum and Maximum Number of Nodes Between Critical Points solution in C++
4. Find the Minimum and Maximum Number of Nodes Between Critical Points solution in Java
5. Find the Minimum and Maximum Number of Nodes Between Critical Points solution in Python
6. Additional Resources

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

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:

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

Example 2:

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:

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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

2058. Find the Minimum and Maximum Number of Nodes Between Critical Points LeetCode Solution in C++

class Solution {
 public:
  vector<int> nodesBetweenCriticalPoints(ListNode* head) {
    int minDistance = INT_MAX;
    int firstMaIndex = -1;
    int prevMaIndex = -1;
    int index = 1;
    ListNode* prev = head;        // Point to the index 0.
    ListNode* curr = head->next;  // Point to the index 1.

    while (curr->next != nullptr) {
      if (curr->val > prev->val && curr->val > curr->next->val ||
          curr->val < prev->val && curr->val < curr->next->val) {
        if (firstMaIndex == -1)  // Only assign once.
          firstMaIndex = index;
        if (prevMaIndex != -1)
          minDistance = min(minDistance, index - prevMaIndex);
        prevMaIndex = index;
      }
      prev = curr;
      curr = curr->next;
      ++index;
    }

    if (minDistance == INT_MAX)
      return {-1, -1};
    return {minDistance, prevMaIndex - firstMaIndex};
  }
};
/* code provided by PROGIEZ */

2058. Find the Minimum and Maximum Number of Nodes Between Critical Points LeetCode Solution in Java

class Solution {
  public int[] nodesBetweenCriticalPoints(ListNode head) {
    int minDistance = Integer.MAX_VALUE;
    int firstMaIndex = -1;
    int prevMaIndex = -1;
    int index = 1;
    ListNode prev = head;      // Point to the index 0.
    ListNode curr = head.next; // Point to the index 1.

    while (curr.next != null) {
      if (curr.val > prev.val && curr.val > curr.next.val ||
          curr.val < prev.val && curr.val < curr.next.val) {
        if (firstMaIndex == -1) // Only assign once.
          firstMaIndex = index;
        if (prevMaIndex != -1)
          minDistance = Math.min(minDistance, index - prevMaIndex);
        prevMaIndex = index;
      }
      prev = curr;
      curr = curr.next;
      ++index;
    }

    if (minDistance == Integer.MAX_VALUE)
      return new int[] {-1, -1};
    return new int[] {minDistance, prevMaIndex - firstMaIndex};
  }
}
// code provided by PROGIEZ

2058. Find the Minimum and Maximum Number of Nodes Between Critical Points LeetCode Solution in Python

class Solution:
  def nodesBetweenCriticalPoints(self, head: ListNode | None) -> list[int]:
    minDistance = math.inf
    firstMaIndex = -1
    prevMaIndex = -1
    index = 1
    prev = head  # Point to the index 0.
    curr = head.next  # Point to the index 1.

    while curr.next:
      if (curr.val > prev.val and curr.val > curr.next.val or
              curr.val < prev.val and curr.val < curr.next.val):
        if firstMaIndex == -1:  # Only assign once.
          firstMaIndex = index
        if prevMaIndex != -1:
          minDistance = min(minDistance, index - prevMaIndex)
        prevMaIndex = index
      prev = curr
      curr = curr.next
      index += 1

    if minDistance == math.inf:
      return [-1, -1]
    return [minDistance, prevMaIndex - firstMaIndex]
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.