Problem Description

This problem asks you to find critical points in a linked list and calculate distances between them.

A critical point is a node that is either a local maxima or local minima:

• A local maxima is a node whose value is strictly greater than both its previous and next nodes
• A local minima is a node whose value is strictly smaller than both its previous and next nodes

Important constraints:

• A node can only be a critical point if it has both a previous node and a next node (so the first and last nodes can never be critical points)

Given a linked list, you need to return an array [minDistance, maxDistance] where:

• minDistance is the minimum distance between any two distinct critical points
• maxDistance is the maximum distance between any two distinct critical points
• Distance is measured as the number of nodes between two critical points

If there are fewer than two critical points in the linked list, return [-1, -1].

For example, if you have a linked list with values [5, 3, 1, 2, 5, 1, 2]:

• Node with value 1 (position 2) is a local minima (3 > 1 < 2)
• Node with value 5 (position 4) is a local maxima (2 < 5 > 1)
• Node with value 1 (position 5) is a local minima (5 > 1 < 2)

The critical points are at positions 2, 4, and 5. The minimum distance is 1 (between positions 4 and 5), and the maximum distance is 3 (between positions 2 and 5).

Intuition

To find critical points, we need to examine three consecutive nodes at a time - the previous, current, and next nodes. This is because a critical point is defined by comparing a node's value with both its neighbors.

The key insight is that we only need to track two things as we traverse the linked list:

1. The position of the first critical point we encounter
2. The position of the last (most recent) critical point we encounter

Why is this sufficient?

For the maximum distance: This will always be the distance between the very first and the very last critical point we find. As we traverse and find new critical points, we can update our last position, and the maximum distance is simply last - first.

For the minimum distance: We need to find the smallest gap between any two consecutive critical points. We don't need to store all critical point positions - we just need to compare each new critical point with the previous one. Each time we find a new critical point, we calculate the distance from the last one and update our minimum if needed.

The traversal strategy is straightforward: maintain a sliding window of three nodes (a, b, c representing previous, current, and next values). Check if b is a critical point by testing:

• Is it a local minima? (a > b < c)
• Is it a local maxima? (a < b > c)

We use a position counter i to track where we are in the linked list, incrementing it as we move forward. This allows us to calculate distances between critical points without needing to store the actual nodes.

If we end up with first == last, it means we found only one or zero critical points, so we return [-1, -1].

Learn more about Linked List patterns.

Solution Approach

The implementation uses a single-pass traversal approach with constant space complexity. Here's how the solution works:

Initialization:

• Set ans = [inf, -inf] to store the minimum and maximum distances. We initialize minimum to infinity and maximum to negative infinity for easy comparison updates.
• Set first = last = -1 to track the positions of the first and most recent critical points found.
• Set i = 0 as a position counter to track the current index in the traversal.

Main Traversal: We traverse the linked list using a while loop with condition head.next.next, which ensures we have at least three nodes to examine (current, next, and next's next).

For each iteration:

1. Extract three consecutive values: a = head.val, b = head.next.val, c = head.next.next.val
2. Check if b (the middle node) is a critical point using the condition: a > b < c or a < b > c
   • a > b < c checks for local minima
   • a < b > c checks for local maxima

Critical Point Processing: When we find a critical point at position i:

• If it's the first critical point (last == -1):
  • Set both first and last to i
• If it's not the first critical point:
  • Update minimum distance: ans[0] = min(ans[0], i - last)
  • Update last = i to track the most recent critical point
  • Update maximum distance: ans[1] = max(ans[1], last - first)

Iteration Update: After checking each position:

• Increment i += 1 to update the position counter
• Move to the next node: head = head.next

Final Result:

• If first == last, it means we found at most one critical point, so return [-1, -1]
• Otherwise, return ans containing [minDistance, maxDistance]

The algorithm efficiently finds all critical points in a single pass with O(n) time complexity and O(1) extra space, only storing the positions of the first and last critical points rather than all critical point positions.

Example Walkthrough

Let's walk through the linked list: [1, 3, 2, 2, 3, 2, 2, 2, 7]

Initial Setup:

• ans = [inf, -inf] (to store min and max distances)
• first = -1, last = -1 (positions of first and last critical points)
• i = 0 (current position counter)

Iteration 1: Position 0

• Three values: a=1, b=3, c=2
• Check: Is 1 > 3 < 2? No. Is 1 < 3 > 2? Yes! (local maxima)
• Found critical point at position 1
• Since last == -1, this is our first critical point
• Update: first = 1, last = 1
• Move forward: i = 1, advance to next node

Iteration 2: Position 1

• Three values: a=3, b=2, c=2
• Check: Is 3 > 2 < 2? No. Is 3 < 2 > 2? No.
• Not a critical point
• Move forward: i = 2, advance to next node

Iteration 3: Position 2

• Three values: a=2, b=2, c=3
• Check: Is 2 > 2 < 3? No. Is 2 < 2 > 3? No.
• Not a critical point
• Move forward: i = 3, advance to next node

Iteration 4: Position 3

• Three values: a=2, b=3, c=2
• Check: Is 2 > 3 < 2? No. Is 2 < 3 > 2? Yes! (local maxima)
• Found critical point at position 4
• Since last != -1, this is not our first
• Update minimum distance: ans[0] = min(inf, 4 - 1) = 3
• Update last = 4
• Update maximum distance: ans[1] = max(-inf, 4 - 1) = 3
• Move forward: i = 4, advance to next node

Iteration 5: Position 4

• Three values: a=3, b=2, c=2
• Check: Is 3 > 2 < 2? No. Is 3 < 2 > 2? No.
• Not a critical point
• Move forward: i = 5, advance to next node

Iteration 6: Position 5

• Three values: a=2, b=2, c=2
• Check: Is 2 > 2 < 2? No. Is 2 < 2 > 2? No.
• Not a critical point
• Move forward: i = 6, advance to next node

Iteration 7: Position 6

• Three values: a=2, b=2, c=7
• Check: Is 2 > 2 < 7? No. Is 2 < 2 > 7? No.
• Not a critical point
• Move forward: i = 7, advance to next node

End of traversal (can't check position 7 as we need a next node after it)

Final Result:

• We found critical points at positions 1 and 4
• first = 1, last = 4
• Since first != last, we have at least 2 critical points
• Return ans = [3, 3]

The minimum distance between critical points is 3, and the maximum distance is also 3 (since we only have 2 critical points).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the linked list. The algorithm traverses the linked list exactly once using a single while loop. In each iteration, it performs constant-time operations: comparing three node values (a, b, c), updating variables, and moving the pointer forward. Since we visit each node once (except the last two nodes due to the head.next.next condition), the total time complexity is linear with respect to the number of nodes.

Space Complexity: O(1). The algorithm uses only a fixed amount of extra space regardless of the input size. The variables used are:

• ans: a list with exactly 2 elements
• first, last, i: integer variables for tracking positions
• a, b, c: temporary variables for storing node values

All these variables require constant space that doesn't grow with the size of the input linked list, resulting in constant space complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Position Tracking

One of the most common mistakes is incorrectly tracking the position of critical points. The position counter should represent the index of the middle node being checked (head.next), not the current head node.

Incorrect approach:

current_position = 0  # Starting at 0
while head.next and head.next.next:
    # Check if head.next is critical
    if is_critical:
        # current_position represents head, not head.next!
        positions.append(current_position)
    current_position += 1
    head = head.next

Correct approach:

current_position = 1  # Start at 1 since we're checking head.next
while head.next and head.next.next:
    # Check if head.next is critical
    if is_critical:
        # current_position correctly represents head.next
        positions.append(current_position)
    current_position += 1
    head = head.next

2. Incorrect Critical Point Detection Logic

A common error is using the wrong comparison operators or forgetting that both conditions must be strict inequalities.

Incorrect approaches:

# Wrong: Using >= or <= instead of strict inequalities
is_critical = (a >= b <= c) or (a <= b >= c)

# Wrong: Using AND instead of OR between conditions
is_critical = (a > b < c) and (a < b > c)

# Wrong: Checking only one type of critical point
is_critical = a > b < c  # Missing local maxima check

Correct approach:

is_local_minimum = previous_val > current_val < next_val
is_local_maximum = previous_val < current_val > next_val
is_critical = is_local_minimum or is_local_maximum

3. Incorrect Distance Calculation

The distance between critical points should be the difference in their positions, not the number of nodes between them plus one.

Incorrect:

distance = current_position - last_position + 1  # Wrong!

Correct:

distance = current_position - last_position  # Correct

4. Not Handling Edge Cases Properly

Failing to check if there are fewer than two critical points before returning the result.

Incorrect approach:

# Returning uninitialized or infinity values
if min_distance == inf:
    return [-1, -1]  # This misses the case where only one critical point exists

Correct approach:

# Check if first and last are the same (meaning 0 or 1 critical points)
if first_critical_point == last_critical_point:
    return [-1, -1]

5. Updating Maximum Distance Incorrectly

A subtle mistake is updating the maximum distance using consecutive critical points instead of the distance from first to current.

Incorrect:

max_distance = max(max_distance, current_position - last_critical_point)  # Wrong!

Correct:

max_distance = max(max_distance, current_position - first_critical_point)
# Or simply: max_distance = last_critical_point - first_critical_point (after updating last)