LeetCode Solutions Blog

Find the Minimum and Maximum Number of Nodes Between Critical Points

Number: 2182

Difficulty: Medium

Paid? No

Problem Description

Given a linked list, a critical point is defined as either a local maxima or a local minima. A node is considered a local maximum if its value is strictly greater than both its previous and next node's values, while it is a local minimum if its value is strictly smaller than both. Note that the first and last nodes are not eligible as they do not have both neighbors. The task is to determine the minimum and maximum distances (in terms of node positions) between any two critical points in the list. If there are fewer than two critical points, return [-1, -1].

Key Insights

Traverse the list while comparing each node (except the first and last) with its previous and next nodes.
Record the index positions (starting from 1) of all critical points.
The minimum distance is found by evaluating consecutive positions, while the maximum distance is the gap between the first and the last critical nodes.
If less than two critical points are found, return [-1, -1].

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list. Space Complexity: O(n) in the worst case for storing indices of critical points.

Solution

The solution involves a single traversal of the linked list. As you iterate from the second node to the second-last node, compare the current node's value with its neighbors to determine if it's a critical point and record its index. After identifying all critical positions, the minimum distance is the smallest difference between consecutive critical indices, and the maximum distance is the difference between the first and last recorded indices. A few edge cases include lists with fewer than two critical points.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def nodesBetweenCriticalPoints(self, head: ListNode):
        # List to store positions (1-indexed) of critical points
        critical_positions = []
        # Initialize pointers: prev, current, and next node pointers
        prev = head
        current = head.next
        index = 2  # current node is at position 2
        # Traverse until the current node does not have a next node
        while current and current.next:
            # Check for local maxima or minima
            if (current.val > prev.val and current.val > current.next.val) or (current.val < prev.val and current.val < current.next.val):
                critical_positions.append(index)
            # Move to the next node in the list
            prev = current
            current = current.next
            index += 1
        # If fewer than 2 critical points, return [-1, -1]
        if len(critical_positions) < 2:
            return [-1, -1]
        # Calculate the minimum distance by evaluating consecutive critical positions
        min_distance = float('inf')
        for i in range(1, len(critical_positions)):
            min_distance = min(min_distance, critical_positions[i] - critical_positions[i - 1])
        # The maximum distance is the difference between the first and last critical points
        max_distance = critical_positions[-1] - critical_positions[0]
        return [min_distance, max_distance]