Find the Minimum and Maximum Number of Nodes Between Critical Points

class Solution {
public:
    vector<int> criticalPointsDistance(ListNode* head) {
        vector<int> distances = {-1, -1};

        // Maximum value for minimizing
        int minimumInterval = INT_MAX;

        // Setup for current, previous node tracking
        ListNode* prev = head;
        ListNode* curr = head->next;
        int idxCurr = 1;
        int idxPrevCritical = 0;
        int idxFirstCritical = 0;

        // Iterate through list
        while (curr->next != nullptr) {
            // Determine if there's a critical point
            if ((curr->val > prev->val && curr->val > curr->next->val) || 
                (curr->val < prev->val && curr->val < curr->next->val)) {
                // Handle the first found critical point
                if (idxPrevCritical == 0) {
                    idxPrevCritical = idxCurr;
                    idxFirstCritical = idxCurr;
                } else {
                    // Update minimum interval and previous index
                    minimumInterval = min(minimumInterval, idxCurr - idxPrevCritical);
                    idxPrevCritical = idxCurr;
                }
            }

            // Advance pointers
            ++idxCurr;
            prev = curr;
            curr = curr->next;
        }

        // Resolve the results if more than one critical point exists
        if (minimumInterval != INT_MAX) {
            int maxInterval = idxPrevCritical - idxFirstCritical;
            distances = {minimumInterval, maxInterval};
        }

        return distances;
    }
};

This C++ solution finds the minimum and maximum number of nodes between critical points in a linked list. Critical points are nodes where the value is either greater than or less than both its adjacent values. Here's how the solution is implemented:

• Initialize a vector called distances with values -1, -1 to hold the minimum and maximum intervals between critical points. If there are less than two critical points, the vector remains as -1, -1.

• Utilize two pointers, prev and curr, to traverse the linked list from the first node. Also maintain idxCurr to keep track of the current node index.

• For each node in the list (except the first and last), check if it is a critical point. A node is considered as a critical point if:

  • It is greater than both its previous and next nodes.
  • It is less than both its previous and next nodes.

• If the current node is a critical point and is the first critical point found, store its index in both idxPrevCritical and idxFirstCritical.

• If another critical point is identified, update the minimumInterval by calculating the difference between the current index and the last previous critical index. Update idxPrevCritical with the current index.

• Continue this until the end of the list is reached.

• After the traversal, if at least two critical points were found (i.e., minimumInterval is not INT_MAX), calculate the maxInterval as the difference between the last and first critical indices and update the distances with both the minimum and maximum intervals.

• Finally, return the distances vector containing the minimum and maximum intervals between critical points if they exist. If there are less than two critical points, it will return -1, -1 indicating no intervals can be determined.

This solution efficiently identifies critical points and measures the intervals by iterating through the linked list once, ensuring a time complexity of O(n), where n is the number of nodes in the list.

class Solution {

    public int[] criticalDistance(ListNode head) {
        int[] distance = { -1, -1 };

        // Minimum distance initialized to a large number
        int minDist = Integer.MAX_VALUE;

        // Position markers and previous critical point data
        ListNode prevNode = head;
        ListNode currNode = head.next;
        int currIndex = 1;
        int lastCritIndex = 0;
        int firstCritIndex = 0;

        while (currNode.next != null) {
            // Determine if current node is a critical point
            if (
                (currNode.val < prevNode.val && currNode.val < currNode.next.val) ||
                (currNode.val > prevNode.val && currNode.val > currNode.next.val)
            ) {
                // Handle first critical point found
                if (lastCritIndex == 0) {
                    lastCritIndex = currIndex;
                    firstCritIndex = currIndex;
                } else {
                    // Update minimum distance
                    minDist = Math.min(
                        minDist,
                        currIndex - lastCritIndex
                    );
                    lastCritIndex = currIndex;
                }
            }

            // Progress the pointers
            currIndex++;
            prevNode = currNode;
            currNode = currNode.next;
        }

        // Check if enough critical points were found
        if (minDist != Integer.MAX_VALUE) {
            int maxDist = lastCritIndex - firstCritIndex;
            distance = new int[] { minDist, maxDist };
        }

        return distance;
    }
}

To find the minimum and maximum number of nodes between critical points in a linked list, follow these steps in Java:

1. Initialize a distance array to {-1, -1} to store the results. If no critical point pairs are found, this will be the result returned.
2. Set minDist to Integer.MAX_VALUE to track the smallest distance encountered.
3. Use nodes prevNode and currNode to iterate through the list starting from the head. Use currIndex to track the current node's index.
4. Initialize lastCritIndex and firstCritIndex to 0 to record indices of critical points.
5. Process each node until the end of the list (currNode.next != null):
   • Check if a node is a critical point by comparing its value with its neighbors. This includes:
     • A node having a value less than both of its neighbors.
     • A node having a value greater than both of its neighbors.
   • If lastCritIndex is 0 (no critical points found yet), set lastCritIndex and firstCritIndex to the current index.
   • If it's not the first critical point, calculate the distance from the last critical point and update minDist if the current distance is smaller.
   • Move lastCritIndex to the current index.
   • Increment currIndex and progress prevNode and currNode.
6. After exiting the loop, check if minDist was updated:
   • Calculate the maximum distance (maxDist) as the difference between the last and first critical indices.
   • Set distance array to { minDist, maxDist }.
7. Return the distance array containing the minimum and maximum distances between critical points. If no critical point pairs are found, the method returns {-1, -1}.

Ensure your linked list contains enough nodes to correctly detect critical points and calculate distances. The above approach provides an efficient method to tackle the problem within a single traversal of the linked list.

class Solution:
    def criticalPointsDistance(self, head: Optional[ListNode]) -> List[int]:
        output = [-1, -1]
        minimum_gap = float("inf")
        
        # Setup to navigate the linked list
        prev = head
        current = head.next
        index = 1
        first_crit = 0
        last_crit = 0

        while current.next is not None:
            if (
                current.val < prev.val and current.val < current.next.val
            ) or (
                current.val > prev.val and current.val > current.next.val
            ):
                # Determine distances when a critical point is found
                if last_crit == 0:
                    last_crit = index
                    first_crit = index
                else:
                    minimum_gap = min(minimum_gap, index - last_crit)
                    last_crit = index

            # Move pointers and index forward
            index += 1
            prev = current
            current = current.next

        if minimum_gap != float("inf"):
            maximum_gap = last_crit - first_crit
            output = [minimum_gap, maximum_gap]

        return output

The provided Python code defines a method criticalPointsDistance in the Solution class for finding the minimum and maximum number of nodes between critical points in a linked list. Here is a summary of how this solution works:

1. Initialize the output list with [-1, -1] to handle cases where there are no valid critical points. minimum_gap is set to infinity to find the minimum distance effectively when encountered.

2. Use pointers, prev and current, to traverse the linked list. Start from the second node because critical points are related to its adjacent nodes.

3. Initialize index to track the current node's position and first_crit and last_crit to store the positions of the first and last critical points found.

4. Loop through the nodes until the second last node (current.next is not None).

5. Check if the current node is a critical point by comparing its value with the adjacent nodes. A node is considered critical if

   • It is a peak (greater than both its neighbors).
   • It is a valley (smaller than both its neighbors).

6. If a critical point is found and last_crit is zero (indicating the first critical point):

   • Set last_crit and first_crit to the current index.
   • Else, update minimum_gap with the difference between the index of the current critical point and the index of the last critical point, and update last_crit to the current index.

7. After the loop, if minimum_gap is less than infinity (indicating that more than one critical point was found):

   • Calculate maximum_gap as the distance between the first and last critical points.
   • Update the output with [minimum_gap, maximum_gap].

8. Return the output, which contains the minimum and maximum gaps between critical points if at least two critical points are found, or [-1, -1] if fewer than two critical points exist.

This solution essentially scans through the linked list to detect critical points and captures their distances to determine the required minimum and maximum gaps.