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

The problem gives us a singly linked list and asks us to identify all of its critical points. A critical point is a node that is either a local maximum or a local minimum.

leetcodemediumlinked-list

LeetCode Problem 2058

Difficulty: 🟡 Medium
Topics: Linked List

Solution

Problem Understanding

The problem gives us a singly linked list and asks us to identify all of its critical points. A critical point is a node that is either a local maximum or a local minimum.

A node is considered a local maximum if its value is strictly greater than both its previous node and its next node. Similarly, a node is considered a local minimum if its value is strictly smaller than both its neighboring nodes.

Because the definition depends on both a previous node and a next node, the first and last nodes of the linked list can never be critical points.

The task is not just to detect critical points, but also to compute two distances:

  • The minimum distance between any two distinct critical points
  • The maximum distance between any two distinct critical points

Distance is measured using node positions in the linked list, starting from index 1 in the examples.

If the linked list contains fewer than two critical points, then there are not enough points to form a pair, so the answer must be [-1, -1].

The input size can be as large as 10^5 nodes. This constraint immediately tells us that we need a linear time solution. Any algorithm with quadratic behavior would be too slow.

An important detail is that the comparisons are strictly greater and strictly smaller. Equal neighboring values do not qualify as critical points. For example, in the sequence [2,2,2], none of the nodes are critical points.

There are several edge cases that can easily cause bugs:

  • Lists with fewer than three nodes cannot contain any critical points
  • Lists with exactly one critical point must return [-1, -1]
  • Consecutive critical points may produce a minimum distance of 1
  • Duplicate values can prevent a node from being critical
  • The first and last nodes must never be considered, even if they appear extreme relative to their single neighbor

Understanding these conditions clearly is essential before designing the algorithm.

Approaches

Brute Force Approach

A straightforward brute force solution would first traverse the linked list and collect the positions of all critical points into an array.

After collecting all critical point indices, we could compare every pair of critical points to compute the minimum and maximum distances.

For example, if the critical points are at positions:

[3, 5, 6, 10]

We could examine all pairs:

  • (3,5)
  • (3,6)
  • (3,10)
  • (5,6)
  • (5,10)
  • (6,10)

For each pair, we compute the distance and update the minimum and maximum.

This method is correct because it explicitly checks every possible pair of critical points. However, if there are k critical points, pairwise comparison requires O(k^2) time. In the worst case, nearly every node could be a critical point, making the complexity approximately O(n^2).

Since n can be 10^5, quadratic behavior is too expensive.

Optimal Approach

The key observation is that we do not need to compare every pair of critical points.

For the minimum distance, the smallest gap will always occur between two consecutive critical points in positional order. If there were a smaller gap between non-consecutive points, then the intermediate critical point would create an even smaller consecutive gap.

For the maximum distance, we only need the distance between the first critical point and the last critical point.

This observation allows us to process the linked list in a single pass:

  • Detect critical points while traversing
  • Track the first critical point
  • Track the previous critical point
  • Continuously update the minimum distance
  • Compute the maximum distance using the current critical point and the first critical point

This reduces the complexity to linear time and constant extra space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Stores all critical points and compares every pair
Optimal O(n) O(1) Single traversal, only tracks essential positions

Algorithm Walkthrough

  1. Initialize traversal pointers.

We use three nodes during traversal:

  • prev, the previous node
  • curr, the current node
  • curr.next, the next node

This allows us to determine whether the current node is a local maximum or local minimum. 2. Track node positions.

Since distance depends on node indices, we maintain a position counter. The current node starts at position 2 because the first node cannot be critical. 3. Detect critical points.

For each node, we check:

  • Local maximum:
curr.val > prev.val AND curr.val > curr.next.val
  • Local minimum:
curr.val < prev.val AND curr.val < curr.next.val

If either condition is true, the current node is a critical point. 4. Store the first critical point.

The first critical point is important because the maximum distance will eventually be:

last_critical_position - first_critical_position

We save its position when we encounter the first critical point. 5. Update the minimum distance.

Every time we find a new critical point, we compare it with the previous critical point.

current_position - previous_critical_position

This works because the smallest possible gap must occur between consecutive critical points. 6. Update the maximum distance.

For every critical point after the first one, we compute:

current_position - first_critical_position

This continuously expands the maximum possible span. 7. Continue traversal.

Move all pointers forward by one node and increment the position counter. 8. Return the result.

If fewer than two critical points exist, return:

[-1, -1]

Otherwise, return:

[minimum_distance, maximum_distance]

Why it works

The algorithm works because it maintains the exact information needed to compute both required distances.

For the minimum distance, only consecutive critical points matter. Any non-consecutive pair must have at least one intermediate critical point, making its distance larger than or equal to some consecutive pair.

For the maximum distance, the farthest possible pair is always the first and last critical points.

By processing the list once and maintaining these invariants, the algorithm guarantees correct results in linear time.

Python Solution

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

from typing import List, Optional

class Solution:
    def nodesBetweenCriticalPoints(
        self,
        head: Optional[ListNode]
    ) -> List[int]:

        prev = head
        curr = head.next

        position = 2

        first_critical = -1
        previous_critical = -1

        min_distance = float("inf")
        max_distance = -1

        while curr and curr.next:

            is_local_max = (
                curr.val > prev.val and
                curr.val > curr.next.val
            )

            is_local_min = (
                curr.val < prev.val and
                curr.val < curr.next.val
            )

            if is_local_max or is_local_min:

                if first_critical == -1:
                    first_critical = position
                else:
                    min_distance = min(
                        min_distance,
                        position - previous_critical
                    )

                    max_distance = (
                        position - first_critical
                    )

                previous_critical = position

            prev = curr
            curr = curr.next
            position += 1

        if max_distance == -1:
            return [-1, -1]

        return [min_distance, max_distance]

The implementation closely follows the algorithm described earlier.

We maintain two traversal pointers, prev and curr, so that we can compare the current node with both neighbors. Since the linked list is singly linked, this rolling window approach is necessary.

The position variable tracks the current node index. We start at 2 because the current node initially points to the second node in the list.

Whenever we detect a critical point, we determine whether it is the first critical point encountered. If it is the first, we simply store its position.

For every later critical point, we update:

  • min_distance using the gap from the previous critical point
  • max_distance using the gap from the first critical point

The variable previous_critical is updated after each critical point so the next comparison can be made correctly.

At the end, if max_distance is still -1, then fewer than two critical points were found, so the required answer is [-1, -1].

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func nodesBetweenCriticalPoints(head *ListNode) []int {

    prev := head
    curr := head.Next

    position := 2

    firstCritical := -1
    previousCritical := -1

    minDistance := int(1e9)
    maxDistance := -1

    for curr != nil && curr.Next != nil {

        isLocalMax :=
            curr.Val > prev.Val &&
                curr.Val > curr.Next.Val

        isLocalMin :=
            curr.Val < prev.Val &&
                curr.Val < curr.Next.Val

        if isLocalMax || isLocalMin {

            if firstCritical == -1 {
                firstCritical = position
            } else {

                distance := position - previousCritical

                if distance < minDistance {
                    minDistance = distance
                }

                maxDistance = position - firstCritical
            }

            previousCritical = position
        }

        prev = curr
        curr = curr.Next
        position++
    }

    if maxDistance == -1 {
        return []int{-1, -1}
    }

    return []int{minDistance, maxDistance}
}

The Go implementation mirrors the Python logic very closely.

Instead of Python's float("inf"), we initialize minDistance with a very large integer value.

Go requires explicit nil checks during traversal, so the loop condition becomes:

for curr != nil && curr.Next != nil

Slices are used for the return value because Go does not have Python-style lists.

Integer overflow is not a concern here because the maximum number of nodes is only 10^5.

Worked Examples

Example 1

Input: [3,1]

There are only two nodes, so no node has both a previous and next neighbor.

Position Value Critical Point?
1 3 No
2 1 No

Result:

[-1, -1]

Example 2

Input: [5,3,1,2,5,1,2]

Critical points occur at positions:

  • Position 3, value 1, local minimum
  • Position 5, value 5, local maximum
  • Position 6, value 1, local minimum

Traversal State

Position Value Critical? firstCritical previousCritical minDistance maxDistance
2 3 No -1 -1 inf -1
3 1 Yes 3 3 inf -1
4 2 No 3 3 inf -1
5 5 Yes 3 5 2 2
6 1 Yes 3 6 1 3

Final result:

[1,3]

Example 3

Input: [1,3,2,2,3,2,2,2,7]

Critical points:

  • Position 2, value 3, local maximum
  • Position 5, value 3, local maximum

Traversal State

Position Value Critical? firstCritical previousCritical minDistance maxDistance
2 3 Yes 2 2 inf -1
3 2 No 2 2 inf -1
4 2 No 2 2 inf -1
5 3 Yes 2 5 3 3

Final result:

[3,3]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited exactly once
Space O(1) Only a few variables are stored

The algorithm performs a single traversal of the linked list. Every node is processed once, and all operations inside the loop take constant time.

No auxiliary data structures proportional to input size are used. The algorithm only maintains a fixed number of variables, so the extra space remains constant.

Test Cases

# Helper utilities for testing

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

solution = Solution()

# Example 1, no critical points
assert solution.nodesBetweenCriticalPoints(
    build_list([3, 1])
) == [-1, -1]

# Example 2, multiple critical points
assert solution.nodesBetweenCriticalPoints(
    build_list([5, 3, 1, 2, 5, 1, 2])
) == [1, 3]

# Example 3, exactly two critical points
assert solution.nodesBetweenCriticalPoints(
    build_list([1, 3, 2, 2, 3, 2, 2, 2, 7])
) == [3, 3]

# Strictly increasing list
assert solution.nodesBetweenCriticalPoints(
    build_list([1, 2, 3, 4, 5])
) == [-1, -1]

# Strictly decreasing list
assert solution.nodesBetweenCriticalPoints(
    build_list([5, 4, 3, 2, 1])
) == [-1, -1]

# Consecutive critical points
assert solution.nodesBetweenCriticalPoints(
    build_list([1, 3, 1, 3, 1])
) == [1, 2]

# Duplicate values prevent critical points
assert solution.nodesBetweenCriticalPoints(
    build_list([2, 2, 2, 2])
) == [-1, -1]

# Exactly one critical point
assert solution.nodesBetweenCriticalPoints(
    build_list([1, 3, 2])
) == [-1, -1]

# Minimum valid critical distance
assert solution.nodesBetweenCriticalPoints(
    build_list([2, 1, 2, 1, 2])
) == [1, 2]

# Large alternating pattern
assert solution.nodesBetweenCriticalPoints(
    build_list([1, 3, 1, 3, 1, 3, 1])
) == [1, 4]
Test Why
[3,1] Validates lists without enough nodes
[5,3,1,2,5,1,2] Tests multiple critical points
[1,3,2,2,3,2,2,2,7] Tests exactly two critical points
Increasing sequence Ensures no false positives
Decreasing sequence Ensures no false positives
Alternating highs and lows Tests consecutive critical points
Duplicate values Verifies strict comparison logic
Single critical point Ensures correct [-1,-1] handling
[2,1,2,1,2] Tests minimum distance of 1
Large alternating pattern Tests repeated updates to min and max

Edge Cases

Lists With Fewer Than Three Nodes

A node can only be critical if it has both a previous and next neighbor. Therefore, lists of length 1 or 2 can never contain critical points.

This case can easily cause pointer access bugs if the implementation assumes neighbors always exist. The traversal loop in the solution avoids this by requiring both curr and curr.next to exist before processing.

Only One Critical Point

It is possible for a linked list to contain exactly one critical point. For example:

[1,3,2]

The middle node is a local maximum, but there is no second critical point to form a pair.

A naive implementation might incorrectly return distances involving uninitialized values. The solution prevents this by only updating distances after encountering the second critical point.

Duplicate Neighbor Values

The problem requires strict inequalities.

For example:

[1,2,2,1]

Neither 2 is a critical point because neither is strictly greater than both neighbors.

This edge case is important because using >= or <= accidentally would produce incorrect results. The implementation explicitly uses strict comparisons:

>
<

which guarantees correct behavior.