#2058

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Find the Minimum and Maximum Number of Nodes Between Critical Points

Find the minimum and maximum number of nodes between critical points in a linked list by identifying local minima and maxima.

linked list

Problem Statement

Given a linked list, a critical point is defined as either a local maxima or a local minima. A node is considered a local maxima if it has a value strictly greater than both the previous and next nodes. A node is a local minima if it has a value strictly smaller than both the previous and next nodes.

Your task is to identify the critical points in the list and calculate the minimum and maximum distances between them. If there are fewer than two critical points, return [-1, -1].

Examples

Example 1

Input: head = [3,1]

Output: [-1,-1]

There are no critical points in [3,1].

Example 2

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

Output: [1,3]

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]

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

Solution Approach

Identify Critical Points

First, iterate through the list to identify all critical points. For each node, check if it is a local minima or local maxima by comparing its value to the previous and next nodes.

Calculate Distances Between Critical Points

Once critical points are identified, calculate the distance between each pair of critical points. Keep track of both the minimum and maximum distances as you process the list.

Edge Case Handling

If fewer than two critical points are found, return [-1, -1]. This accounts for cases where there are no critical points or only one critical point in the list.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity is O(n) due to the single pass required to identify critical points and calculate distances. The space complexity is O(1) as only a few variables are needed for calculation and storage.

What Interviewers Usually Probe

The candidate should efficiently traverse the linked list and handle edge cases with minimal overhead.
Look for the ability to optimize the identification of local minima and maxima in a single pass.
The candidate must consider and handle edge cases where there are fewer than two critical points.

Common Pitfalls or Variants

Common pitfalls

Overlooking edge cases where fewer than two critical points exist, leading to incorrect output.
Failing to handle linked lists of small sizes (e.g., lists with only two nodes).
Inefficient traversal or unnecessary extra space usage when iterating through the list.

Follow-up variants

Consider variations where the list may contain duplicate values that affect local maxima or minima.
Explore a version where the linked list is doubly linked, which might simplify some edge cases.
Modify the problem to find critical points based on other criteria, such as being greater than or less than neighboring nodes for multiple comparisons.

FAQ

What are critical points in this problem?

Critical points are nodes in a linked list that are either local minima or local maxima, where the node's value is either strictly smaller or larger than both its neighbors.

How do you calculate the minimum and maximum distances between critical points?

Once all critical points are identified, the minimum distance is the smallest gap between two critical points, and the maximum distance is the largest gap.

What should I do if the linked list has fewer than two critical points?

If there are fewer than two critical points, return [-1, -1] as there are no valid distances to measure.

How does linked list pointer manipulation apply to this problem?

The problem involves traversing a linked list and using pointer manipulation to identify critical points and calculate distances, making efficient pointer traversal key to solving this problem.

Can this problem be solved in less than O(n) time?

No, solving this problem requires at least one pass through the linked list to identify critical points, so the time complexity is O(n).

terminal

Solution

Solution 1: Direct Traversal

Based on the problem description, we need to find the positions of the first and last critical points in the linked list, $\textit{first}$ and $\textit{last}$, respectively. This allows us to calculate the maximum distance $\textit{maxDistance} = \textit{last} - \textit{first}$. For the minimum distance $\textit{minDistance}$, we need to traverse the linked list, calculate the distance between two adjacent critical points, and take the minimum value.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def nodesBetweenCriticalPoints(self, head: Optional[ListNode]) -> List[int]:
        ans = [inf, -inf]
        first = last = -1
        i = 0
        while head.next.next:
            a, b, c = head.val, head.next.val, head.next.next.val
            if a > b < c or a < b > c:
                if last == -1:
                    first = last = i
                else:
                    ans[0] = min(ans[0], i - last)
                    last = i
                    ans[1] = max(ans[1], last - first)
            i += 1
            head = head.next
        return [-1, -1] if first == last else ans

Continue Practicing

#2074 reverse nodes in even length groups #2095 delete the middle node of a linked list #2130 maximum twin sum of a linked list