LeetCode 2058. Find the Minimum and Maximum Number of Nodes Between Critical Points Java Solution

Problem Description

• Problem: LeetCode 2058. Nodes Between Critical Points

• Description: Given a singly linked list, we need to find the minimum and maximum distance between nodes that are local maxima (a value greater than its neighbors) or local minima (a value smaller than its neighbors).

  • A local maxima is a node whose value is greater than its neighbors, e.g., in 3-9-6, 9 is a local maxima.

  • A local minima is a node whose value is smaller than its neighbors, e.g., in 6-1-7, 1 is a local minima.

Approach

• Idea:

  • Traverse the linked list to identify nodes that are local maxima or local minima and record their positions.

  • Calculate the minimum and maximum distance between these recorded positions.

• Algorithm:

  1. Traverse the linked list and check each node to see if it is a local maxima or minima by comparing it to its previous and next nodes.

  2. Skip the last two nodes in the list since they cannot be local maxima or minima.

  3. Track the indices of these critical points.

  4. Use the list of indices to compute the minimum and maximum distances between the critical points.

  5. As the indices are collected during traversal, they are naturally ordered.

  6. The maximum distance is the difference between the last and first indices in the list.

  7. The minimum distance is found by comparing consecutive differences between indices.

Code

class Solution {
    public int[] nodesBetweenCriticalPoints(ListNode head) {
        ListNode temp = head;
        List<Integer> list = new ArrayList<>();
        int index = 1;
        int[] result = {-1, -1};

        while (temp != null && temp.next != null && temp.next.next != null) {
            ListNode prev = temp;
            ListNode curr = temp.next;
            ListNode next = temp.next.next;

            if ((curr.val > prev.val && curr.val > next.val) ||
                (curr.val < prev.val && curr.val < next.val)) {
                list.add(index);
            }

            temp = temp.next;
            index++;
        }

        int n = list.size();
        if (n < 2) {
            return result;
        }

        int minDistance = Integer.MAX_VALUE;

        for (int i = 1; i < n; i++) {
            minDistance = Math.min(minDistance, list.get(i) - list.get(i - 1));
        }

        int maxDistance = list.get(n - 1) - list.get(0);

        result[0] = minDistance;
        result[1] = maxDistance;

        return result;
    }
}

Conclusion

• Time Complexity: The algorithm requires O(n) time to traverse the linked list once to find the critical points and O(n) time to calculate the distances between the critical points. Therefore, the overall time complexity is O(n).

• Space Complexity: The algorithm uses a constant amount of extra space (O(1)), excluding the space needed for the input and output.