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.

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].

Examples

Example 1:

graph LR;
3 --> 1
  
1
2
3

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

Example 2:

graph LR;
5 --> 3 --> 1 --> 2 --> E(5) --> A(1) --> B(2)

style 1 fill:#FF9933,stroke:#333,stroke-width:2px;
style E fill:#00FF00,stroke:#333,stroke-width:2px;
style A fill:#FF9933,stroke:#333,stroke-width:2px;
  
1
2
3
4
5
6
7
8

Input: head = [5,3,1,2,5,1,2]
Output: [1,3]
Explanation: There are three critical points (minimas and maximas are shown as orange and green respectively):
- [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:

graph LR;
1 --> 3 --> 2 --> B(2) --> C(3) --> C1(2) --> C2(2) --> C3(2) --> 7

style 3 fill:#00FF00,stroke:#333,stroke-width:2px;
style C fill:#00FF00,stroke:#333,stroke-width:2px;
  
1
2
3
4
5
6
7
8

Input: head = [1,3,2,2,3,2,2,2,7]
Output: [3,3]
Explanation: There are two critical points (both maximas shown as green):
- [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.

Solution

Method 1 - Two Pass

In first iteration we traverse the linked list and create a list storing all the critical points. Then, in second iteration find the max and min distance between these critical points.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
    public int[] nodesBetweenCriticalPoints(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return new int[]{-1, -1};
        }

        List<Integer> criticalPoints = new ArrayList<>();
        ListNode prev = head;
        ListNode curr = head.next;
        int position = 1;

        while (curr.next != null) {
            if ((curr.val > prev.val && curr.val > curr.next.val) ||
                (curr.val < prev.val && curr.val < curr.next.val)) {
                criticalPoints.add(position);
            }
            prev = curr;
            curr = curr.next;
            position++;
        }

        if (criticalPoints.size() < 2) {
            return new int[]{-1, -1};
        }

        int minDistance = Integer.MAX_VALUE;
        int maxDistance = criticalPoints.get(criticalPoints.size() - 1) - criticalPoints.get(0);

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

        return new int[]{minDistance, maxDistance};
    }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)

Method 2 - One pass tracking critical points

We can start iterating the list, and keep track of following positions:

  • pos - Position of the node in the linked list
  • currPos - Position of the current critical point
  • prevPos - Position of the previous critical point
  • firstPos - Position where we find the first critical point. We will use it to find the

Then

1
2

minDist = Math.min(minDist, currPos - prevPos)
maxDist = currPos - firstPos

Here is the video explanation:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {

	public int[] nodesBetweenCriticalPoints(ListNode head) {
		ListNode prev = head;
		ListNode curr = head.next;
		int[] ans = { -1, -1 };
		int prevPos = -1, currPos = -1, firstPos = -1, pos = 0;

		while (curr.next != null) {
			if ((curr.val < prev.val && curr.val  <  curr.next.val) || (curr.val > prev.val && curr.val > curr.next.val)) {
				// local
				prevPos = currPos;
				currPos = pos;

				if (firstPos == -1) {
					firstPos = pos;
				}

				if (prevPos != -1) {
					if (ans[0] == -1) ans[0] = currPos - prevPos;
					else ans[0] = Math.min(ans[0], currPos - prevPos);
					ans[1] = pos - firstPos;
				}
			}

			pos++;
			prev = curr;
			curr = curr.next;
		}

		return ans;
	}
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)