Skip to content

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

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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};
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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};
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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]