Find the Minimum and Maximum Number of Nodes Between Critical Points — LeetCode 2058 Python Solution

MediumLinked List

Problem: #2058
Pattern: Linked List
Reading time: 4 min
Source: leetcode.com

The problem

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.

Example

Input: head = [3,1]
Output: [-1,-1]
Explanation: There are no critical points in [3,1].

Python solution

Python

# 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

Complexity

Measure	Complexity
Time	O(n), where n is the length of the linked list
Space	O(1) auxiliary

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Linked List.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points?: LeetCode 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points is rated Medium on LeetCode.
What is the time complexity of LeetCode 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points?: The Python solution on this page runs in O(n), where n is the length of the linked list.
What is the space complexity of LeetCode 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points?: The Python solution on this page uses O(1) auxiliary space.
What topics does LeetCode 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points cover?: LeetCode 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points is tagged Linked List on LeetCode.