Find the Minimum and Maximum Number of Nodes Between Critical Points

Med

#1874Time: O(N), where N is the number of nodes in the linked list. The first pass to find critical points takes O(N) time. The second pass over the list of critical point indices takes O(K) time, where K is the number of critical points (K <= N). Thus, the total time complexity is O(N).Space: O(K), where K is the number of critical points. In the worst-case scenario (e.g., an alternating sequence like 1, 5, 1, 5, ...), K can be proportional to N, leading to a space complexity of O(N).2 companies

Data structures

Linked List

Companies

josh technology Info Edge

Prompt

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⁵

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves two main steps. First, we traverse the entire linked list to identify all critical points and store their indices in a separate list. In the second step, we process this list of indices to calculate the minimum and maximum distances.

Algorithm

Initialize an empty list criticalIndices to store the indices of critical points.
Initialize three pointers, prev = head, curr = head.next, and an index counter starting at 2.
Traverse the linked list from the second node until the second-to-last node (while curr.next != null).
In each iteration, check if curr is a critical point by comparing its value with prev.val and curr.next.val.
- A node is a local maxima if curr.val > prev.val && curr.val > curr.next.val.
- A node is a local minima if curr.val < prev.val && curr.val < curr.next.val.
If curr is a critical point, add its current index to the criticalIndices list.
After the traversal, check if the size of criticalIndices is less than 2. If so, return [-1, -1].
Calculate the maxDistance as the difference between the last and first elements in criticalIndices.
Calculate the minDistance by iterating through criticalIndices and finding the minimum difference between any two adjacent indices.
Return [minDistance, maxDistance].

Walkthrough

We begin by initializing an empty list, say criticalIndices, to store the 1-based indices of all critical points. We then iterate through the linked list, starting from the second node up to the second-to-last node, as a critical point must have both a predecessor and a successor. We use three pointers: prev, curr, and next to check the condition for a critical point. For each node curr, we check if its value is strictly greater than both prev.val and next.val (local maxima) or strictly smaller than both (local minima). If it is, we add its index to our criticalIndices list. After the traversal is complete, we check the size of criticalIndices. If it's less than 2, it's impossible to form a pair of distinct critical points, so we return [-1, -1]. Otherwise, the maximum distance is the difference between the last and the first index in the list. To find the minimum distance, we iterate through the criticalIndices list and find the minimum difference between any two adjacent indices. Finally, we return the calculated [minDistance, maxDistance].

1import java.util.ArrayList;2import java.util.List;3 4/**5 * Definition for singly-linked list.6 * public class ListNode {7 *     int val;8 *     ListNode next;9 *     ListNode() {}10 *     ListNode(int val) { this.val = val; }11 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }12 * }13 */14class Solution {15    public int[] nodesBetweenCriticalPoints(ListNode head) {16        if (head == null || head.next == null || head.next.next == null) {17            return new int[]{-1, -1};18        }19 20        List<Integer> criticalIndices = new ArrayList<>();21        ListNode prev = head;22        ListNode curr = head.next;23        int index = 2;24 25        while (curr.next != null) {26            ListNode next = curr.next;27            if ((curr.val > prev.val && curr.val > next.val) || 28                (curr.val < prev.val && curr.val < next.val)) {29                criticalIndices.add(index);30            }31            prev = curr;32            curr = next;33            index++;34        }35 36        if (criticalIndices.size() < 2) {37            return new int[]{-1, -1};38        }39 40        int minDistance = Integer.MAX_VALUE;41        for (int i = 1; i < criticalIndices.size(); i++) {42            minDistance = Math.min(minDistance, criticalIndices.get(i) - criticalIndices.get(i - 1));43        }44 45        int maxDistance = criticalIndices.get(criticalIndices.size() - 1) - criticalIndices.get(0);46 47        return new int[]{minDistance, maxDistance};48    }49}

Complexity

Time

O(N), where N is the number of nodes in the linked list. The first pass to find critical points takes O(N) time. The second pass over the list of critical point indices takes O(K) time, where K is the number of critical points (K <= N). Thus, the total time complexity is O(N).

Space

O(K), where K is the number of critical points. In the worst-case scenario (e.g., an alternating sequence like 1, 5, 1, 5, ...), K can be proportional to N, leading to a space complexity of O(N).

Trade-offs

Pros

The logic is straightforward and easy to understand as it separates the problem into two distinct phases: finding points and then calculating distances.

Cons

Uses O(K) extra space, where K is the number of critical points. In the worst case, this can be O(N).
Requires two passes over the data (one on the linked list, one on the list of indices), which is less efficient than a single-pass solution.

This optimized approach calculates the minimum and maximum distances in a single traversal of the linked list. By keeping track of the indices of the first and most recent critical points found, we can update the distances on the fly, thus avoiding the need for extra storage.

Algorithm

Initialize minDistance = Integer.MAX_VALUE, firstCriticalIndex = -1, and prevCriticalIndex = -1.
Initialize prev = head, curr = head.next, and index = 2.
Iterate while curr.next is not null:
- Let next = curr.next.
- Check if curr is a critical point.
- If it is:
  - If firstCriticalIndex is -1, set firstCriticalIndex = index.
  - If prevCriticalIndex is not -1, update minDistance = min(minDistance, index - prevCriticalIndex).
  - Update prevCriticalIndex = index.
- Update pointers: prev = curr, curr = next.
- Increment index.
After the loop, if minDistance is still Integer.MAX_VALUE (meaning fewer than two critical points were found), return [-1, -1].
Calculate maxDistance = prevCriticalIndex - firstCriticalIndex.
Return [minDistance, maxDistance].

Walkthrough

We iterate through the linked list once, keeping track of the previous node, current node, and the current node's index. We also need a few variables: firstCriticalIndex to store the index of the very first critical point, prevCriticalIndex to store the index of the previously found critical point, and minDistance initialized to a very large value. The traversal starts from the second node. For each node, we check if it's a critical point (local maxima or minima). When we find a critical point at index i: if firstCriticalIndex has not been set yet, we set it to i. If prevCriticalIndex has been set (meaning we've found at least one critical point before this one), we can calculate the distance to the previous critical point: i - prevCriticalIndex. We then update minDistance with the minimum of its current value and this new distance. After processing, we always update prevCriticalIndex to the current index i, as it becomes the 'previous' critical point for the next one we find. After the loop finishes, if we have found fewer than two critical points (i.e., minDistance is still at its initial large value), we return [-1, -1]. Otherwise, the maxDistance is simply the difference between the last critical point we found (prevCriticalIndex) and the first one (firstCriticalIndex). We then return [minDistance, maxDistance].

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public int[] nodesBetweenCriticalPoints(ListNode head) {13        if (head == null || head.next == null || head.next.next == null) {14            return new int[]{-1, -1};15        }16 17        int minDistance = Integer.MAX_VALUE;18        int firstCriticalIndex = -1;19        int prevCriticalIndex = -1;20 21        ListNode prev = head;22        ListNode curr = head.next;23        int index = 2;24 25        while (curr.next != null) {26            ListNode next = curr.next;27            if ((curr.val > prev.val && curr.val > next.val) || 28                (curr.val < prev.val && curr.val < next.val)) {29                30                if (firstCriticalIndex == -1) {31                    firstCriticalIndex = index;32                }33                34                if (prevCriticalIndex != -1) {35                    minDistance = Math.min(minDistance, index - prevCriticalIndex);36                }37                38                prevCriticalIndex = index;39            }40            prev = curr;41            curr = next;42            index++;43        }44 45        if (minDistance == Integer.MAX_VALUE) {46            return new int[]{-1, -1};47        }48 49        int maxDistance = prevCriticalIndex - firstCriticalIndex;50        return new int[]{minDistance, maxDistance};51    }52}

Complexity

Time

O(N), where N is the number of nodes. We perform a single pass through the linked list.

Space

O(1). We only use a few variables to store state (`minDistance`, `firstCriticalIndex`, `prevCriticalIndex`, `index`), regardless of the size of the input list. This is a significant improvement over the two-pass approach.

Trade-offs

Pros

Highly efficient in terms of memory, using only a constant amount of extra space.
Processes the list in a single pass, making it faster in practice by avoiding the overhead of intermediate data structures.

Cons

The logic can be slightly more complex to follow compared to the two-pass approach due to the need to manage multiple state variables (firstCriticalIndex, prevCriticalIndex) within a single loop.

Solutions

Solution

1/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public int [] nodesBetweenCriticalPoints ( ListNode head ) { ListNode prev = head ; ListNode curr = head . next ; int first = 0 , last = 0 ; int i = 1 ; int [] ans = new int [] { Integer . MAX_VALUE , Integer . MIN_VALUE }; while ( curr . next != null ) { if ( curr . val < Math . min ( prev . val , curr . next . val ) || curr . val > Math . max ( prev . val , curr . next . val )) { if ( last == 0 ) { first = i ; last = i ; } else { ans [ 0 ] = Math . min ( ans [ 0 ], i - last ); ans [ 1 ] = i - first ; last = i ; } } ++ i ; prev = curr ; curr = curr . next ; } return first == last ? new int [] {- 1 , - 1 } : ans ; } }

1/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: vector < int > nodesBetweenCriticalPoints ( ListNode * head ) { ListNode * prev = head ; ListNode * curr = head -> next ; int first = 0 , last = 0 ; int i = 1 ; vector < int > ans ( 2 , INT_MAX ); while ( curr -> next ) { if ( curr -> val < min ( prev -> val , curr -> next -> val ) || curr -> val > max ( prev -> val , curr -> next -> val )) { if ( last == 0 ) first = i ; else { ans [ 0 ] = min ( ans [ 0 ], i - last ); ans [ 1 ] = i - first ; } last = i ; } ++ i ; prev = curr ; curr = curr -> next ; } if ( first == last ) return { - 1 , - 1 }; return ans ; } };

1# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def nodesBetweenCriticalPoints ( self , head : Optional [ ListNode ]) -> List [ int ]: prev , curr = head , head . next first = last = None i = 1 ans = [ inf , - inf ] while curr . next : if curr . val < min ( prev . val , curr . next . val ) or curr . val > max ( prev . val , curr . next . val ): if last is None : first = last = i else : ans [ 0 ] = min ( ans [ 0 ], i - last ) ans [ 1 ] = i - first last = i i += 1 prev , curr = curr , curr . next return ans if first != last else [ - 1 , - 1 ]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem