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:
[2, 105].1 <= Node.val <= 105In #2058 Find the Minimum and Maximum Number of Nodes Between Critical Points, the key idea is to identify critical points in a linked list. A node is considered critical if it forms a local minima or local maxima compared to its immediate neighbors. Since linked lists are sequential structures, the most efficient strategy is to traverse the list once while tracking node positions.
During traversal, compare each node’s value with its previous and next node to determine whether it is a critical point. Record the index of the first critical point and keep updating the index of the previous one found. This allows you to compute the minimum distance between consecutive critical points and the maximum distance between the first and current critical point.
If fewer than two critical points exist, return [-1, -1]. This approach works efficiently with a single pass through the list, giving a time complexity of O(n) and constant O(1) extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Single-pass traversal tracking critical indices | O(n) | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
The maximum distance must be the distance between the first and last critical point.
For each adjacent critical point, calculate the difference and check if it is the minimum distance.
In this approach, we traverse the linked list in a single pass, collecting the positions of critical points (local minima and maxima) along the way. We maintain two variables, `firstCritical` and `lastCritical`, to track the position of the first and the last critical points encountered. Additionally, we calculate the minimum distance between consecutive critical points using a running minimum distance variable.
Finally, the maximum distance is the distance between the first and last critical points if at least two critical points are found. Otherwise, return [-1, -1] if fewer than two critical points exist.
The time complexity of this solution is O(n), where n is the number of nodes in the linked list, because we traverse the list only once. The space complexity is O(1), since we only use a static amount of additional space.
1class ListNode {
2 int val;
3 ListNode next;
4 ListNode(int x) { val = x; next =
The Java solution keeps track of previous and current nodes to identify critical points during a single traversal. It updates indices and calculates distances while iterating through the list nodes, finally returning the required distances between critical points.
This approach resolves the problem using two full passes over the linked list for clearer data separation. In the first traversal, we gather all the indices of critical points into a list. During the second traversal over the list of critical points, we calculate the minimum and maximum distances between critical point pairs.
This method enhances clarity by separately collecting and then processing data, although it might sacrifice some execution time compared to a single-pass solution.
The time complexity is O(n) as it traverses the list twice, but the proportional dependence on n remains. Space complexity is O(k), where k is the number of critical points stored.
1class ListNode:
2 def __init__(self, val=0
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
A node is a critical point if its value is either strictly greater than both neighbors (local maximum) or strictly smaller than both neighbors (local minimum). You determine this by comparing the current node with its previous and next nodes during traversal.
Problems involving linked list traversal and local extrema detection are common in technical interviews, including FAANG-style rounds. This question tests pointer manipulation, single-pass optimization, and careful edge case handling.
A singly linked list is the core data structure in this problem. The algorithm only requires pointer traversal and index tracking, so no additional complex data structures are needed beyond a few variables.
The optimal approach is a single-pass traversal of the linked list. While iterating, identify local minima or maxima and track their indices to compute minimum and maximum distances. This method runs in O(n) time and uses O(1) extra space.
This Python version uses two loops over a linked list. The first loop extracts indices of critical points, and the second loop computes the desired statistics from them, aiding in understandability and ensuring comprehensive error handling.