We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Minimum and Maximum Number of Nodes Between Critical Points

Difficulty: Medium

Problem Description

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. 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].

Key Insights

  • Critical points can only occur if there are at least three nodes in the list.
  • Local maxima and minima need to be identified by comparing each node's value with its previous and next nodes.
  • Distances between critical points are based on the indices of these points in the list.
  • To find the minimum and maximum distances, we can keep track of all critical point indices and compute the differences.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list, as we traverse the list once to identify critical points.
Space Complexity: O(k), where k is the number of critical points, to store their indices.

Solution

To solve the problem, we will traverse the linked list while maintaining a list of indices of the critical points. At each node, we will check if it's a local maxima or minima by comparing its value with its neighbors. If we find critical points, we will compute the minimum and maximum distances based on their indices.

Code Solutions

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

def nodesBetweenCriticalPoints(head: ListNode):
    critical_points = []
    index = 0
    current = head
    
    while current and current.next and current.next.next:
        if (current.val < current.next.val > current.next.next.val) or (current.val > current.next.val < current.next.next.val):
            critical_points.append(index + 1)  # Append the index of the critical point
        current = current.next
        index += 1

    if len(critical_points) < 2:
        return [-1, -1]

    min_distance = float('inf')
    max_distance = 0

    for i in range(len(critical_points) - 1):
        distance = critical_points[i + 1] - critical_points[i]
        min_distance = min(min_distance, distance)
        max_distance = max(max_distance, critical_points[-1] - critical_points[i])

    return [min_distance, max_distance]
← Back to All Questions