2058. Find the Minimum and Maximum Number of Nodes Between Critical Points
Approach
Single pass tracking first and last critical point indices; compute min gap between consecutive.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Linked list problems often use the fast/slow pointer (Floyd's algorithm) for cycle detection and finding the middle, and dummy head nodes for clean insertion/deletion. Reverse operations should be done iteratively to avoid stack overflow on large lists.
The two-pointer technique places pointers at different positions (often the two ends) and moves them toward each other. It turns O(n²) nested loops into O(n) sweeps for problems like pair sums, removing duplicates, and container capacity. Works best on sorted or partitioned arrays.
// Approach: Single pass tracking first and last critical point indices; compute min gap between consecutive.
// Time: O(n) Space: O(1)
public class ListNode
{
public int val;
public ListNode next;
public ListNode(int val = 0, ListNode next = null)
{
this.val = val;
this.next = next;
}
}
public class Solution
{
public int[] NodesBetweenCriticalPoints(ListNode head)
{
int minDistance = Int32.MaxValue;
int firstMaIndex = -1, prevMaIndex = -1, index = 1;
ListNode prev = head;
ListNode curr = head.next;
while (curr.next != null)
{
if (curr.val > prev.val && curr.val > curr.next.val ||
curr.val < prev.val && curr.val < curr.next.val)
{
if (firstMaIndex == -1)
firstMaIndex = index;
if (prevMaIndex != -1)
minDistance = Math.Min(minDistance, index - prevMaIndex);
prevMaIndex = index;
}
prev = curr;
curr = curr.next;
index++;
}
if (minDistance == Int32.MaxValue)
return new int[] { -1, -1 };
return new int[] { minDistance, prevMaIndex - firstMaIndex };
}
}