Sponsored
Sponsored
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 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
We iterate over the linked list using a while loop, checking if the current node is a local maxima or minima by comparing it with its previous and next nodes. We track the indices of the first and last critical points discovered. Whenever another critical point is found, we update the minimum distance using the index difference from the last critical point.
If fewer than two critical points are found, we return [-1, -1]; otherwise, the result is an array of [minDistance, maxDistance].
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,
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.