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

Let's teach this from absolute zero, same structure as before.

---

1. Problem in Very Simple Language

You're given a linked list — a chain of nodes, where each node holds a number and points to the next node in the chain (we'll explain "linked list" fully in a moment).

Walking through this chain, some nodes are special. A node is called a critical point if it's either:

a local maxima — its value is strictly bigger than both the node right before it AND the node right after it (like a little "peak"), or a local minima — its value is strictly smaller than both the node right before it AND the node right after it (like a little "valley").

Important rule: the very first node and the very last node can never be critical points, because a first node has no "previous" node, and a last node has no "next" node — and you need both neighbors to even check.

Once you've found all the critical points (there could be zero, one, two, or many), you look at their positions (not their values — their positions/indices in the chain) and compute:

INLINECODE0 = the smallest gap (in positions) between any two critical points. INLINECODE1 = the largest gap (in positions) between any two critical points.

If there are fewer than 2 critical points total, you can't compute any distance, so you return INLINECODE2.

What's given: the head (starting node) of a linked list. What to find: all critical points' positions, then the smallest and largest gap between any two of them. What to return: a 2-element array INLINECODE3.

---

2. Real-Life Analogy

Imagine you're walking along a mountain trail, and at various points along the trail there are little signposts marking your distance from the start (like "3 km", "4 km", "5 km", ...). As you walk, the trail's elevation goes up and down. Some spots are exactly at the top of a little hill (higher than the ground just before and just after you) — those are "peaks." Some spots are exactly at the bottom of a little dip (lower than the ground just before and just after) — those are "valleys."

Peaks and valleys are your "critical points." You want to know: among all these peaks and valleys, what's the shortest distance (in km, using those signposts) between any two of them, and what's the longest distance between any two of them? Note you're comparing signpost numbers (positions), not how high or low the ground was at each point.

---

3. Important Programming Concepts I Need First

Linked List

Concept: A linked list is a chain of "nodes." Each node holds a value AND a pointer (a reference/arrow) to the next node in the chain. Unlike an array, you can't jump straight to "position 5" — you have to walk node by node, starting from the INLINECODE4 (the first node), following the INLINECODE5 pointers one at a time. Simple Example: INLINECODE6. Here, the node holding INLINECODE7 points to the node holding INLINECODE8, which points to INLINECODE9, which points to INLINECODE10, which points to INLINECODE11 (meaning "nothing after this, I'm the last one"). Why we need it: The input to this problem is a linked list, not a plain array, so we must walk through it using INLINECODE12 instead of indexing with INLINECODE13.

Node (and its two parts)

Concept: In Java, a node here is an object with two fields: INLINECODE14 (the number it stores) and INLINECODE15 (a reference to the next node, or INLINECODE16 if it's the last one). Example: INLINECODE17 gives you the number; INLINECODE18 gives you the next node in the chain (or INLINECODE19). Why we need it: We'll be constantly reading INLINECODE20 to compare values, and following INLINECODE21 to move forward.

Variable

Concept: A named "box" to store a value for later use. Example: INLINECODE22 remembers "the previous node's value was 3." Why we need it: As we walk the list, we need to remember "what was the previous node's value" and "what was the previous node's position," since we don't have array indexing to look backward.

Loop (specifically, a INLINECODE23 loop)

Concept: Repeats an action until some condition becomes false. A INLINECODE24 loop is especially natural for linked lists because we don't know the length in advance — we just keep going INLINECODE25. Example: INLINECODE26 walks through every node exactly once. Why we need it: We must walk the entire linked list from head to end, and a INLINECODE27 loop (checking for INLINECODE28) is the standard way to do that.

If/else

Concept: Lets the program branch based on a condition. Example: "If the current value is bigger than both neighbors, mark it as a local maxima." Why we need it: Detecting whether a node is a critical point (and if so, whether it's a max or min) is fundamentally an if/else decision.

Index / Position tracking (manual, since linked lists have no built-in indexing)

Concept: Since a linked list doesn't let you ask "what's at position 5?" directly, if we want to know where something is, we have to count it ourselves as we walk — using a variable that increases by 1 each step. Why we need it: INLINECODE29 and INLINECODE30 are computed using positions, so we must track "which position am I currently at?" manually with a counter variable.

Function / Method

Concept: A reusable named block of code. Why we need it: Not strictly required to introduce a new one here, but our solution itself is a method (INLINECODE31) that we'll build step by step.

Array (for the final output)

Concept: A small fixed list of values. Example: INLINECODE32 creates a 2-box array; INLINECODE33 and INLINECODE34 are the two boxes. Why we need it: Our answer must be returned as a 2-element array: INLINECODE35.

Time Complexity

We'll use this at the end to explain why our solution is fast enough for lists up to 100,000 nodes long.

---

4. Understand the Input

Take Example 2: CODEBLOCK0

This represents a linked list: INLINECODE36.

Let's number the positions starting from 0, just like array indices, even though it's technically a linked list:

Position	0	1	2	3	4	5	6
Value	5	3	1	2	5	1	2

INLINECODE37 points to the very first node, whose value is INLINECODE38. Each number is connected to the next by a INLINECODE39 pointer, ending in INLINECODE40 after the last node (INLINECODE41 at position 6). We are looking for: which positions are local maxima or minima, then the min/max distance between them. Why can't position 0 (value INLINECODE42) or position 6 (value INLINECODE43) ever be critical points? Because position 0 has no "previous" node, and position 6 has no "next" node — the rule explicitly requires both neighbors to exist.

---

5. Understand the Output

Output: INLINECODE44

Walking through, we check every "middle" position (1 through 5, since 0 and 6 can't qualify): Position 1 (value INLINECODE45): previous is INLINECODE46, next is INLINECODE47. Is INLINECODE48 bigger than both? No (INLINECODE49). Is INLINECODE50 smaller than both? No (INLINECODE51). Not critical. Position 2 (value INLINECODE52): previous is INLINECODE53, next is INLINECODE54. Is INLINECODE55 smaller than both INLINECODE56 and INLINECODE57? Yes! Local minima at position 2. Position 3 (value INLINECODE58): previous is INLINECODE59, next is INLINECODE60. Not bigger than both, not smaller than both. Not critical. Position 4 (value INLINECODE61): previous is INLINECODE62, next is INLINECODE63. Is INLINECODE64 bigger than both INLINECODE65 and INLINECODE66? Yes! Local maxima at position 4. Position 5 (value INLINECODE67): previous is INLINECODE68, next is INLINECODE69. Is INLINECODE70 smaller than both INLINECODE71 and INLINECODE72? Yes! Local minima at position 5. So critical points are at positions INLINECODE73. Gaps between consecutive critical points: INLINECODE74, and INLINECODE75. INLINECODE76 = the smallest of all pairwise gaps = INLINECODE77 (between positions 4 and 5). INLINECODE78 = the gap between the very first and very last critical point = INLINECODE79 (between positions 2 and 5). Final answer: INLINECODE80 — matches!

---

6. Solve the Example Manually

Let's carefully solve Example 2 by hand, walking node by node like a human (and like our code eventually will).

INLINECODE81, positions 0 through 6.

We can only check a node for critical-point status once we know its previous value, its own value, and its next value. Let's walk through step by step, sliding a little 3-node window along the list:

(We never check position 0 or position 6, since they lack a full previous/next pair.)

Critical points found, in order: position 2, position 4, position 5.

Now let's track two things as we would while scanning left to right: The position of the very first critical point we ever found (call it INLINECODE82) — this only gets set once, and never changes after that. The position of the most recently seen critical point (call it INLINECODE83) — this updates every time we find a new one, and each time we update it, we can immediately check "how far is this one from the previous one?" to possibly update our running INLINECODE84.

| Critical point found at position | firstCriticalPos | prevCriticalPos (before this one) | Gap to prevCriticalPos | Running minDistance |

After scanning everything: INLINECODE85, and the last critical point we found was at position INLINECODE86. INLINECODE87 (this is always the gap between the very first and very last critical point — more on why in Section 7). INLINECODE88 (the smallest gap we ever saw between two consecutive critical points, tracked as we went).

Final answer: INLINECODE89 ✔️ matches!

---

7. Think Like a Programmer

What do I know? I can walk the list node by node, and at each node (except the first and last), I can check its previous, current, and next values. What do I need to find? The smallest and largest gap between any two critical points' positions. What can I try? The most direct idea: first collect all critical point positions into a list, then afterward, compare every pair of positions to find the smallest and largest gap. What happens if I try every possibility? If there are INLINECODE90 critical points, comparing every pair takes about INLINECODE91 comparisons. In the worst case INLINECODE92 could be close to INLINECODE93 (roughly half of all nodes could be peaks/valleys alternating), so this could be slow-ish, though not catastrophically slow. But we can do even better — we don't actually need to compare every pair. Can I make it faster? Yes! Here's the key realization: the maximum distance is always simply the gap between the very first critical point and the very last critical point. Why? Because any two critical points that are both strictly between the first and last one will always have a smaller gap between them than the outermost pair does (since positions only increase as we walk forward, the first-to-last span is the biggest possible span you could ever measure). So for max distance, we don't need to compare all pairs at all — just remember the first and last critical positions. For minimum distance, on the other hand, the smallest gap is always between two consecutive critical points (right next to each other in our found-order), never between two that have another critical point in between them (since skipping over a middle one can only make the gap bigger, not smaller). So we only ever need to compare each critical point to the previous critical point we found — never to older ones further back. What information should I remember? As we scan: the position of the first critical point ever found, the position of the most recently found critical point (to compute consecutive gaps), and running best values for min/max distance. What pattern do I notice? We can find the entire answer in one single pass through the list, without ever storing all critical points in a separate list at all!

---

8. Start With the Brute Force Solution

Brute force idea: First, walk the entire list once and record the position of every critical point into a list (e.g., an INLINECODE94). Then, use two nested loops to compare every pair of positions in that list, tracking the smallest and largest difference found.

Why it works: By checking literally every pair, we're guaranteed to find the true minimum and maximum gap — no risk of missing anything.

Why it's correct: Exhaustively comparing all pairs can never miss the actual smallest or largest gap, since every possible pair gets checked.

Time complexity: INLINECODE95 to walk the list and find critical points, plus INLINECODE96 to compare all pairs, where INLINECODE97 is the number of critical points found (and INLINECODE98 can be up to roughly INLINECODE99). So worst case, this is INLINECODE100.

Space complexity: INLINECODE101 to store the list of critical point positions.

CODEBLOCK1

---

9. Explain the Brute Force Code Line by Line

INLINECODE102 — an empty, growable list where we'll collect the positions of every critical point we find. INLINECODE103 — we set up two "pointers" (references): INLINECODE104 starts at the first node, INLINECODE105 starts at the second node. This way, INLINECODE106 is always the node we're currently examining, and INLINECODE107 is always the node right before it. INLINECODE108 — since INLINECODE109 starts at the second node (index 1, if we imagine array-style indexing), we initialize our position counter to INLINECODE110 to match. INLINECODE111 — we keep looping as long as INLINECODE112 exists AND INLINECODE113 has a next node — because without both a previous node (INLINECODE114, guaranteed to exist here) and a next node (INLINECODE115), INLINECODE116 can never be a critical point, so there's no point checking it. INLINECODE117 — checks: is the current node's value strictly bigger than both its previous and next neighbor's values? If so, it's a local maxima. INLINECODE118 — same idea, but checking for strictly smaller than both, meaning local minima. INLINECODE119 — if either condition is true, we record this position as a critical point. INLINECODE120 — this is how we "slide the window" forward: what was INLINECODE121 becomes the new INLINECODE122, we move INLINECODE123 one step further using INLINECODE124, and we increment our manual position counter to match. After the loop, INLINECODE125 holds every critical point's position, in increasing order (since we found them while walking left to right). INLINECODE126 — the problem says if there are fewer than 2 critical points, we can't compute any distance, so we return INLINECODE127 immediately. The nested INLINECODE128 loops — INLINECODE129 picks one critical position, INLINECODE130 (starting right after INLINECODE131) picks another; together they examine every possible pair exactly once (never comparing something to itself, and never comparing the same pair twice). INLINECODE132 — since our list is in increasing order and INLINECODE133, this gap is always positive. INLINECODE134 — we keep running track of the smallest and largest gap seen across all pairs.

---

10. Why Is the Brute Force Solution Not Ideal?

Imagine a linked list with 100,000 nodes, arranged so that roughly half of them (about 50,000) end up being critical points (values zig-zagging up and down the whole way, like INLINECODE135). Comparing every pair among 50,000 critical points means roughly INLINECODE136, which is over a billion comparisons — way too slow for a single test case. We need a way to compute the answer using far fewer comparisons.

---

11. Find the Better Approach

"Can we avoid doing unnecessary work?"

Yes — remember our two realizations from Section 7:

1. INLINECODE137 only ever needs the FIRST and LAST critical point positions — nothing in between matters at all for computing it. 2. INLINECODE138 only ever needs to compare each critical point to the ONE right before it (the "previous" critical point found), never to any critical point further back.

CODEBLOCK2

---

⭐ Key Insight

Before the insight

We were thinking we'd need to gather every critical point first, then go back and compare all of them against each other to find the best min/max gaps.

The problem

Comparing all pairs is wasteful — most of that comparison work turns out to be completely unnecessary once we understand the structure of the positions.

The insight

Since critical point positions only ever increase as we scan through the list (we find them in left-to-right order, never out of order), two facts become guaranteed: The gap between the very first critical point found and the very last one found is always at least as large as the gap between any other two critical points — because any "inner" pair is, by definition, squeezed inside that outer span. So INLINECODE139, always, no comparison needed. The smallest possible gap between any two critical points must be between two that are immediately next to each other in the found-order — if you skip over a middle critical point to compare two further-apart ones, that gap can only be equal to or bigger than the sum of the smaller consecutive gaps, never smaller. So we only ever need to compare consecutive pairs, which we can do live, as we scan, using just one "previous critical point" variable.

After the insight

We never need to store the full list of critical positions at all (though it's fine to, for clarity) — we can compute the entire answer in a single left-to-right pass, updating a few running variables: the first critical position found, the most recently found critical position, and running min/max values.

---

13. Dry Run the Optimized Solution

Let's dry-run Example 3 to see a slightly different case.

CODEBLOCK3

We scan positions 1 through 7 (positions 0 and 8 can never qualify). After the full scan: INLINECODE140, INLINECODE141, INLINECODE142 (the only consecutive gap we found, between positions 1 and 4).

INLINECODE143.

Final answer: INLINECODE144 ✔️ matches the expected output! This also nicely demonstrates why equal neighboring values (like the repeated INLINECODE145s) never count as critical — the condition requires strictly greater or smaller.

---

14. Optimized Code

CODEBLOCK4

CODEBLOCK5

---

15. Explain Optimized Code Line by Line

INLINECODE146 — will hold the position of the first critical point we ever find. We start it at INLINECODE147 to mean \"not found yet\" (a valid position can never actually be INLINECODE148, so this is a safe \"empty\" marker). INLINECODE149 — will hold the position of the most recently found critical point, updated every time we find a new one. Also starts as \"not found yet.\" INLINECODE150 — we start this at the largest possible integer value, so that the very first real gap we compute is guaranteed to be smaller than it, and will correctly become our new minimum (this is the same \"start with an impossibly bad value, then improve it\" trick from other problems). INLINECODE151 — our manual position counter, matching where INLINECODE152 starts (the second node). INLINECODE153 — set up our two walking references, same as brute force: INLINECODE154 trails one step behind INLINECODE155. INLINECODE156 — we loop as long as INLINECODE157 has a next node (meaning INLINECODE158 isn't the very last node). We don't need to separately check INLINECODE159 here, because INLINECODE160 starts at INLINECODE161 and the problem guarantees at least 2 nodes exist, so INLINECODE162 is never INLINECODE163 going into a valid iteration. INLINECODE164 — exactly the same critical-point check as brute force: strictly bigger than both neighbors, or strictly smaller than both. INLINECODE165 — whenever we find a critical point: INLINECODE166 — if this is the first critical point we've ever seen (our \"first\" tracker is still unset), we record its position as INLINECODE167. We do NOT compute a gap here, since there's nothing before it to compare to yet. INLINECODE168 — otherwise, this is at least our second critical point (or later), so we compute the gap between this one and the immediately previous critical point we found, and update INLINECODE169 if this gap is smaller than anything seen so far. INLINECODE170 — regardless of which branch we took, we always update \"most recently found critical point\" to be this one, so the next critical point (if any) can correctly compare against it. INLINECODE171 — slide our window forward by one node, same as brute force. After the loop: INLINECODE172 — this checks: did we find zero critical points at all (INLINECODE173 never got set), OR did we find exactly one critical point (in which case INLINECODE174 would have only ever been set to the same value as INLINECODE175, since the INLINECODE176 branch — which updates INLINECODE177 after the first — never ran)? Either way, that's fewer than 2 critical points, so we return INLINECODE178. INLINECODE179 — by the time we reach here, INLINECODE180 holds the position of the very last critical point found (since it gets overwritten every time), and INLINECODE181 holds the very first one — exactly the pair we proved gives the maximum distance. INLINECODE182 — return our final answer.

---

16. Test With Multiple Examples

Example 1 — Normal Case (fewer than 2 critical points)

INLINECODE183. Here INLINECODE184 is the node with value INLINECODE185, and INLINECODE186 is INLINECODE187 immediately — so the INLINECODE188 loop body never executes even once! INLINECODE189 stays INLINECODE190 → Output: INLINECODE191 ✔️

Example 2 — Different Case

INLINECODE192 → dry-ran conceptually in Section 6 → Output: INLINECODE193 ✔️

Example 3 — Edge Case

INLINECODE194 → dry-ran in Section 13 → Output: INLINECODE195 ✔️

---

17. Edge Cases

List has only 2 nodes → INLINECODE196 is INLINECODE197 right away, loop never runs, INLINECODE198 stays INLINECODE199 → return INLINECODE200 (there's no possible \"middle\" node with both a previous and next neighbor). List has exactly one critical point → INLINECODE201 gets set once, but INLINECODE202 ends up equal to INLINECODE203 (since the INLINECODE204 branch that would update it differently never executes for a second point) → we correctly detect this via INLINECODE205 and return INLINECODE206. All values are identical (e.g., INLINECODE207) → no node is ever strictly bigger or smaller than its neighbors → zero critical points found → INLINECODE208. Critical points are adjacent in value pattern but not truly \"back to back\" in a zigzag — doesn't matter; our algorithm only cares about positions of found critical points, which naturally handles any spacing. Very long list (up to 100,000 nodes) — our single-pass approach handles this efficiently, unlike the brute-force pairwise comparison. First and last actual list nodes look locally \"extreme\" — irrelevant, since they're structurally excluded from ever being checked (no previous/next respectively) by our loop bounds.

---

18. Time Complexity

What is time complexity? It's a way of estimating how the amount of work grows as the input grows — like noticing that reading a book twice as long takes roughly twice as long to read, using a general rule rather than a stopwatch.

CODEBLOCK6

Why: In the optimized version, we visit each node exactly once, and at each node we do only a small, fixed amount of work (a couple of comparisons and variable updates) — no matter how many critical points we've found so far, checking a new one against \"the previous one\" is always instant, since we only keep track of a single number (INLINECODE209), never a growing list to search through. Compare this to brute force, where as more critical points pile up, comparing all of them to each other gets slower and slower — like re-checking your entire guest list every time one more person RSVPs, instead of just noting \"how far apart is this RSVP from the last one?\"

---

19. Space Complexity

We only ever store a small, fixed number of extra variables: INLINECODE210, INLINECODE211, INLINECODE212, INLINECODE213, INLINECODE214, INLINECODE215 — none of these grow as the list grows. We don't build any list, array, or other structure that scales with INLINECODE216 (unlike the brute-force version, which stored every critical position in an INLINECODE217).

So extra space used is INLINECODE218 — constant, regardless of how long the linked list is.

---

20. Common Mistakes Beginners Make

❌ \"I should check if the head node or the last node is a critical point too.\" ✅ The problem explicitly rules this out — a node can only be critical if it has both a previous and a next node, which the first and last nodes never do.

❌ \"Local maxima/minima just means bigger or smaller than the immediate neighbors — equal counts too.\" ✅ The comparison must be strictly greater or strictly smaller. If a neighbor has the exact same value, that node cannot be a critical point (this trips people up with repeated/plateau values, like in Example 3).

❌ \"I need to store all critical positions in a list and compare every pair to be safe.\" ✅ You only need the first and last found positions for INLINECODE219, and consecutive pairs for INLINECODE220 — storing everything and comparing all pairs is unnecessary extra work (and slower).

❌ \"I can just use array indices since it's basically like an array.\" ✅ It's a linked list — there's no INLINECODE221 here. You must manually track position with a counter variable as you walk using INLINECODE222, since linked lists don't support direct indexing.

❌ \"I'll check INLINECODE223 in my loop condition.\" ✅ Since we need INLINECODE224 to exist too (to check the \"next neighbor\"), the real stopping condition should be based on INLINECODE225 — and since the problem guarantees at least 2 nodes, INLINECODE226 itself (starting at INLINECODE227) is safely non-null throughout.

---

21. How to Recognize This Pattern in Other Problems

Watch for these signal phrases:

CODEBLOCK7

Whenever you're scanning a sequence and only need to compare each element to its immediate neighbors (not the whole sequence), and the final answer involves gaps between found positions, think: track "first found" and "most recent found" as you scan — you rarely need to store everything and compare all pairs.

---

22. Interview Thinking

CODEBLOCK8

Applied here: recognizing that max-distance only needs the two extreme endpoints, and min-distance only needs consecutive comparisons, collapses an apparent \"compare everything\" problem into a simple single pass.

---

23. Mini Challenge

Try these before checking the answers:

1. Why is it guaranteed that INLINECODE228 is always exactly INLINECODE229, and never some other pair? 2. If we find critical points at positions INLINECODE230, what is INLINECODE231? (Hint: you don't need to check INLINECODE232 or INLINECODE233.) 3. Why do we start INLINECODE234 at INLINECODE235 instead of, say, INLINECODE236?

Answer to Mini Challenge

1. Because critical point positions are discovered in strictly increasing order as we scan left to right, the very first one is the smallest position and the very last one is the largest position among all critical points — so the gap between them is automatically the largest possible gap you could form from any two critical points in the whole set. 2. INLINECODE237, from the gap INLINECODE238, since INLINECODE239 and INLINECODE240 are both larger. We only ever needed to compare consecutive pairs: INLINECODE241, INLINECODE242, INLINECODE243 — never the non-consecutive ones. 3. We start at INLINECODE244 because we're about to repeatedly take the minimum* of this variable and newly computed gaps — starting \"impossibly high\" guarantees that the very first real gap we compute will correctly replace it, the same trick used whenever you're hunting for a running minimum.

---

24. Final Revision

🧠 Problem in One Sentence

Find every local max/min node in a linked list (by position), then report the smallest and largest gap between any two of them.

🔑 Main Idea

The maximum distance is always between the very first and very last critical point found; the minimum distance is always between two consecutive critical points — so a single left-to-right pass, tracking only \"first found\" and \"most recently found,\" is enough.

⚙️ Algorithm

1. Walk the list with two references (INLINECODE245, INLINECODE246), tracking position manually. 2. At each \"middle\" node (has both a previous and next), check if it's a local maxima or minima. 3. On finding a critical point: if it's the first one, just record its position. Otherwise, compute the gap to the previous critical point and update INLINECODE247. 4. Always update \"most recently found critical point\" after checking. 5. After the scan: if fewer than 2 critical points were found, return INLINECODE248. Otherwise, INLINECODE249 = last found position − first found position.

⏱️ Complexity

Time: INLINECODE250 Space: INLINECODE251

🎯 Pattern to Remember

\"Scan once, track first + most-recent\" beats \"collect everything, then compare all pairs\" whenever max needs only the extremes and min needs only neighbors.

---

25. Beginner Quiz

1. (Understanding) Why can the head node and the tail node of the list never be critical points, no matter what their values are? 2. (Basic concept) What's the difference between checking INLINECODE252 (not strict... wait, it IS strict) versus using INLINECODE253 instead of INLINECODE254 — why would that be wrong here? 3. (Logic) Why don't we ever need to compare a critical point to one that is two or more critical points back (not the immediately previous one)? 4. (Dry run) For INLINECODE255, find all critical points (by position) and compute INLINECODE256. 5. (Complexity/pattern) Why is this solution INLINECODE257 and INLINECODE258 space instead of needing an array to store all node values first, and what key phrase in the problem (\"previous and next node\") should make you think of a \"sliding trio\" scan rather than random access?