Find the Minimum and Maximum Number of Nodes Between Critical Points

Medium

Asked by:

42 views

Topics:

Linked Lists

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.

Note that a node can only be a local maxima/minima if there exists both a previous node and a 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].

Example 1:

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

Example 2:

Input: head = [5,3,1,2,5,1,2]
Output: [1,3]
Explanation: There are three critical points:
- [5,3,1,2,5,1,2]: The third node is a local minima because 1 is less than 3 and 2.
- [5,3,1,2,5,1,2]: The fifth node is a local maxima because 5 is greater than 2 and 1.
- [5,3,1,2,5,1,2]: The sixth node is a local minima because 1 is less than 5 and 2.
The minimum distance is between the fifth and the sixth node. minDistance = 6 - 5 = 1.
The maximum distance is between the third and the sixth node. maxDistance = 6 - 3 = 3.

Example 3:

Input: head = [1,3,2,2,3,2,2,2,7]
Output: [3,3]
Explanation: There are two critical points:
- [1,3,2,2,3,2,2,2,7]: The second node is a local maxima because 3 is greater than 1 and 2.
- [1,3,2,2,3,2,2,2,7]: The fifth node is a local maxima because 3 is greater than 2 and 2.
Both the minimum and maximum distances are between the second and the fifth node.
Thus, minDistance and maxDistance is 5 - 2 = 3.
Note that the last node is not considered a local maxima because it does not have a next node.

Constraints:

The number of nodes in the list is in the range [2, 10⁵].
1 <= Node.val <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What should I return if there are fewer than two critical points in the linked list?
Can the values in the linked list be negative, zero, or floating-point numbers?
Could you define more formally what constitutes a 'critical point' when the neighboring nodes have the same value as the current node?
What are the constraints on the number of nodes in the linked list?
Is it guaranteed that the linked list is valid (e.g., no cycles)?

Brute Force Solution

Approach

We're looking for special spots in a path, called 'critical points'. The brute force method involves checking every single position along the path to see if it's a critical point, and then measuring the distances between them to find the smallest and largest.

Here's how the algorithm would work step-by-step:

Go through the path, one spot at a time.
For each spot, check if it is higher or lower than both of its neighbors to determine if it is a critical point.
Make a list of all the critical points you find as you go.
Once you have the list, look at every possible pair of critical points.
For each pair, calculate the distance between them.
Keep track of the smallest distance you find between any two critical points.
Keep track of the largest distance you find between any two critical points.
After checking all possible pairs, report the smallest and largest distances you found.

Code Implementation

def find_min_max_distance_between_critical_points_brute_force(heights):
    critical_points_indices = []
    number_of_heights = len(heights)

    # Find critical points.
    for index in range(1, number_of_heights - 1):
        if heights[index] > heights[index - 1] and heights[index] > heights[index + 1]:
            critical_points_indices.append(index)
        elif heights[index] < heights[index - 1] and heights[index] < heights[index + 1]:
            critical_points_indices.append(index)

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

    minimum_distance = float('inf')
    maximum_distance = 0

    # Iterate through all pairs of critical points.
    for first_critical_point_index in range(len(critical_points_indices)):

        # Only consider critical points after the current point.
        for second_critical_point_index in range(first_critical_point_index + 1, len(critical_points_indices)):
            
            distance = abs(critical_points_indices[first_critical_point_index] - critical_points_indices[second_critical_point_index])

            # Update the minimum distance if necessary
            minimum_distance = min(minimum_distance, distance)

            # Update the maximum distance if necessary
            maximum_distance = max(maximum_distance, distance)

    return [minimum_distance, maximum_distance]

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the input array of size n to identify critical points. This initial scan takes O(n) time. After identifying the critical points, the algorithm considers every possible pair of critical points to find the minimum and maximum distances. In the worst-case scenario, every point could be a critical point, resulting in O(n) critical points. Comparing all pairs of critical points then requires nested loops, leading to approximately n * n/2 comparisons. Therefore, the overall time complexity is dominated by the pairwise comparison of critical points, simplifying to O(n²).

Space Complexity

O(N) – The algorithm creates a list of critical points. In the worst case, every point along the path could be a critical point, leading to a list of size N, where N is the number of spots in the path. Therefore, the auxiliary space required for storing the critical points scales linearly with the input size N. No other significant data structures are used beyond the critical points list.

Optimal Solution

Approach

To find the smallest and largest distances between critical points in a sequence, we first need to identify these critical points. Then, instead of comparing every pair of critical points, we'll cleverly track the minimum and maximum distances as we go through the list once.

Here's how the algorithm would work step-by-step:

Go through the sequence and mark down the locations of all critical points. A critical point is where the value is either a local peak (higher than its neighbors) or a local valley (lower than its neighbors).
If you find fewer than two critical points, there's no distance to calculate, so you're done.
Keep track of the smallest distance seen so far between two consecutive critical points.
Keep track of the largest distance seen so far between any two critical points.
Go through the list of critical points. For each critical point, calculate the distance to the next critical point.
If the distance to the next critical point is smaller than the smallest distance recorded, update the smallest distance.
Find the distance between the first and last critical point. This gives you the maximum possible separation.
The smallest and largest distances you've kept track of are your answers.

Code Implementation

def find_min_max_critical(nodes):
    critical_points = []
    # Identify critical points, skipping the ends.
    for i in range(1, len(nodes) - 1):
        if (nodes[i] > nodes[i - 1] and nodes[i] > nodes[i + 1]) or \
           (nodes[i] < nodes[i - 1] and nodes[i] < nodes[i + 1]):
            critical_points.append(i)

    # Not enough critical points, cannot determine min/max distances.
    if len(critical_points) < 2:
        return [-1, -1]

    min_distance = float('inf')
    max_distance = critical_points[-1] - critical_points[0]

    # Iterate over critical points.
    for i in range(len(critical_points) - 1):

        #Calc distance to next point.
        distance = critical_points[i + 1] - critical_points[i]

        #Update min distance
        min_distance = min(min_distance, distance)

    return [min_distance, max_distance]

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input list of size n (where n is the number of nodes) once to identify critical points. Then, it iterates through the list of critical points, which in the worst case could also be of size n, to calculate the minimum and maximum distances between them. Both iterations are linear with respect to the input size n; therefore, the time complexity is O(n).

Space Complexity

O(N) – The algorithm identifies critical points and stores their locations. In the worst-case scenario, every point in the input sequence could be a critical point, leading to a list of N indices. This list of critical point locations dominates the auxiliary space. Therefore, the space complexity is O(N), where N is the number of elements in the input sequence.

Edge Cases

Case	How to Handle
Null or empty input list	Return [-1, -1] indicating no critical points found and thus no distance.
List with fewer than 3 elements	Return [-1, -1] because a critical point requires at least three elements to compare.
List with only one critical point	Return [-1, -1] because you need at least two critical points to calculate min/max distances.
List with all elements having the same value	Return [-1, -1] as there are no critical points possible.
Adjacent critical points	Ensure the minimum distance calculation correctly handles consecutive critical points with a distance of 1.
Critical points appearing at the beginning and end of the list	The algorithm should correctly identify and use these boundary critical points when calculating minimum and maximum distances.
Large input list leading to potential integer overflow when calculating distances	Use long integer type for storing distances to avoid overflow issues.
Input list contains duplicate values that create multiple critical points	The algorithm must accurately identify all valid critical points even if they are next to each other because of duplicate values.

Null or empty input list

How to Handle:

Return [-1, -1] indicating no critical points found and thus no distance.

List with fewer than 3 elements

How to Handle:

Return [-1, -1] because a critical point requires at least three elements to compare.

List with only one critical point

How to Handle:

Return [-1, -1] because you need at least two critical points to calculate min/max distances.

List with all elements having the same value

How to Handle:

Return [-1, -1] as there are no critical points possible.

Adjacent critical points

How to Handle:

Ensure the minimum distance calculation correctly handles consecutive critical points with a distance of 1.

Critical points appearing at the beginning and end of the list

How to Handle:

The algorithm should correctly identify and use these boundary critical points when calculating minimum and maximum distances.

Large input list leading to potential integer overflow when calculating distances

How to Handle:

Use long integer type for storing distances to avoid overflow issues.

Input list contains duplicate values that create multiple critical points

How to Handle:

The algorithm must accurately identify all valid critical points even if they are next to each other because of duplicate values.