Leetcode 2058 - Medium - Find the Minimum and Maximum Number of Nodes Between Critical Points

Leetcode 2058 - O(n) solution.py

"""
We can optimise by recognising that:
- max_dist will always be (last - first)
- min_dist will always be from one pair of adjacent critical points, so we can calculate it as we run through the list

Time: O(n)
- We only run through the linked list once
Space: O(n)
- We create only a handful of extra variables, none of which are iterables or callables
"""
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def nodesBetweenCriticalPoints(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: List[int]
        """
        cur_cp = None
        first_cp = None
        i = 0
        prev = None          # val[i-1]
        prev_trend = None    # val[i-1] - val[i-2] (positive means trending up, negative means trending down)
        min_dist = float('inf')
        
        """
        Local max: more than both surrounding vals
         #
        ###
         ^

        Local min: less than both surrounding vals
        # #
        ###
         ^
        """

        while head is not None:
            val = head.val
        
            if prev_trend is not None:
                if (val > prev and prev_trend < 0) or (val < prev and prev_trend > 0):
                    cur_cp = i - 1
                    if first_cp == None:
                        first_cp = cur_cp
                        # Save the first critical point so that we can use it for max_dist later
                    else:
                        dist = cur_cp - prev_cp
                        if dist < min_dist:
                            min_dist = dist
                    prev_cp = cur_cp
                prev_trend = val - prev
            elif prev is not None:
                prev_trend = val - prev

            prev = val

            i += 1
            head = head.next

        if first_cp == None or cur_cp == first_cp:
            return [-1, -1]
            
        return [min_dist, cur_cp - first_cp]

Leetcode 2058 - Solution.py

"""
The basic solution requires us to recognise when a value causes a change in a trend, e.g. from going down to going up, or vise-versa
- If the trend was going down, and now it's going up, we found a local minima (& record it)
- If the trend was going up, and now it's going down, we found a local maxima (& record it)
- If the trend has flattened, we reset

Then we can loop through the list of critical points and calculate the min and max distances.
This is pretty good, but not optimal.

Time: O(n + m) 
- We need to run through the linked list first, then the list of critical points
Space: O(n + m) 
- n = linked list
- m = list of critical points
"""
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def nodesBetweenCriticalPoints(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: List[int]
        """
        result = [-1, -1]
        crit_points = []
        i = 0
        prev = None          # val[i-1]
        prev_trend = None    # val[i-1] - val[i-2] (positive means trending up, negative means trending down)
        
        """
        Local max: more than both surrounding vals
         #
        ###
         ^

        Local min: less than both surrounding vals
        # #
        ###
         ^
        """

        while head is not None:
            val = head.val
        
            if prev_trend is not None:
                if val > prev and prev_trend < 0:
                    # prev was a local min
                    crit_points.append(i - 1)    

                if val < prev and prev_trend > 0:
                    # prev was a local max
                    crit_points.append(i - 1)

                prev_trend = val - prev
            elif prev is not None:
                prev_trend = val - prev

            prev = val

            i += 1
            head = head.next

        if len(crit_points) < 2:
            return result

        max_dist = crit_points[len(crit_points)-1] - crit_points[0]

        min_dist = float('inf')
        for i in range(1, len(crit_points)):
            dist = crit_points[i] - crit_points[i-1]
            if dist < min_dist:
                min_dist = dist

        return [min_dist, max_dist]