3903. Smallest Stable Index I
Difficulty: Easy | Published on 2026-09-05
Let's teach this one from absolute zero, same structure as always.
1. Problem in Very Simple Language
You have an array of numbers, INLINECODE0, and a threshold number INLINECODE1.
For every single index INLINECODE2 in the array, you compute a special value called its instability score, defined as:
Look at all the numbers from the very start of the array up through index INLINECODE3 (inclusive) — find the biggest number among them. Look at all the numbers from index INLINECODE4 (inclusive) all the way to the very end of the array — find the smallest number among them. Subtract: INLINECODE5. That's the instability score for index INLINECODE6.
Notice something important: index INLINECODE7 is included in both halves — once when finding the max of "everything up to and including INLINECODE8," and once when finding the min of "everything from INLINECODE9 to the end, including INLINECODE10."
An index is called stable if its instability score is INLINECODE11.
Goal: find the smallest index that is stable. If no index qualifies, return INLINECODE12.
What's given: the array INLINECODE13, and threshold INLINECODE14. What to find: for each index, the max-of-left-part minus min-of-right-part, then the earliest index where this is small enough. What to return: that smallest stable index, or INLINECODE15.
2. Real-Life Analogy
Imagine you're standing at some point along a hiking trail, looking both ways. Looking backward (toward the start of the trail, including where you're standing), you note the highest peak you can see behind you. Looking forward (toward the end of the trail, including where you're standing), you note the lowest valley you can see ahead of you.
Your "instability score" at this spot is: how much higher is that tallest peak behind you compared to that lowest valley ahead of you? If that difference is small enough (≤ some tolerance INLINECODE16), you'd call this spot "stable" — the terrain immediately behind and ahead doesn't swing too wildly. You want to find the very first (leftmost) spot along the trail where this is true.
3. Important Programming Concepts I Need First
Array
Concept: A numbered list of values, indexed from 0. Example: INLINECODE17 — index 0 holds INLINECODE18, index 3 holds INLINECODE19. Why we need it: Our input and all our reasoning happen over this array.Variable
Concept: A named "box" holding a value we can update. Example: INLINECODE20 Why we need it: We'll track a "max so far" and a "min so far" as we scan.Loop
Concept: Repeats an action across every item in a list. Example: "For each index, update the running maximum." Why we need it: We need to scan the array (potentially more than once) to build up the information needed at every index.If/else
Concept: Branching based on a condition. Example: "If this index's instability score is ≤ k, we found our answer." Why we need it: Checking the stability condition, and updating running max/min, both require decisions.Prefix Max (a new but simple pattern)
Concept: A prefix max array is a helper array where position INLINECODE21 stores "the biggest value seen from the start of the array up through position INLINECODE22." You build it left-to-right, and each entry only ever needs to compare the previous prefix max to the current element — no need to rescan everything from the start each time. Example: For INLINECODE23: prefixMax = INLINECODE24 (since INLINECODE25 is the biggest seen at every point from index 0 onward). Why we need it: The problem needs "max of everything from 0 to INLINECODE26" for every INLINECODE27 — precomputing this once, left to right, avoids recalculating that max from scratch for every index.Suffix Min (the mirror-image idea)
Concept: A suffix min array stores, at position INLINECODE28, "the smallest value seen from position INLINECODE29 all the way to the end." You build it right-to-left, comparing each entry to the next suffix min. Example: For INLINECODE30: suffixMin = INLINECODE31 (reading right to left: at index 3, min is 4; at index 2, min of INLINECODE32 is 1; at index 1, min of INLINECODE33 is 0; at index 0, min of INLINECODE34 is 0). Why we need it: The problem needs "min of everything from INLINECODE35 to the end" for every INLINECODE36 — precomputing this once, right to left, similarly avoids repeated rescanning.Time Complexity
We'll use this to explain why our approach (with INLINECODE37 up to only 100 here, admittedly tiny) is efficient and clean.4. Understand the Input
Take Example 1: CODEBLOCK0
| Index | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| Value | 5 | 0 | 1 | 4 |
5. Understand the Output
Output: INLINECODE49
At index 0: max of INLINECODE50 = 5; min of INLINECODE51 = 0; score = INLINECODE52. Not ≤ 3. At index 1: max of INLINECODE53 = 5; min of INLINECODE54 = 0; score = INLINECODE55. Not ≤ 3. At index 2: max of INLINECODE56 = 5; min of INLINECODE57 = 1; score = INLINECODE58. Not ≤ 3. At index 3: max of INLINECODE59 = 5; min of INLINECODE60 = 4; score = INLINECODE61. This is ≤ 3! Stable. Since index 3 is the first index where the score drops to ≤ k, the answer is INLINECODE62.6. Solve the Example Manually
Let's build the two helper arrays by hand for INLINECODE63.
Step 1: Build the prefix max array, left to right.
| Index | Value | Compare to previous prefix max | New prefix max |
|---|---|---|---|
| 0 | 5 | (nothing before) start with 5 | 5 |
| 1 | 0 | max(5, 0) = 5 | 5 |
| 2 | 1 | max(5, 1) = 5 | 5 |
| 3 | 4 | max(5, 4) = 5 | 5 |
Step 2: Build the suffix min array, right to left.
| Index | Value | Compare to next suffix min | New suffix min |
|---|---|---|---|
| 3 | 4 | (nothing after) start with 4 | 4 |
| 2 | 1 | min(1, 4) = 1 | 1 |
| 1 | 0 | min(0, 1) = 0 | 0 |
| 0 | 5 | min(5, 0) = 0 | 0 |
Step 3: Scan left to right, compute INLINECODE66, and stop at the first index where it's ≤ k.
| Index | prefixMax | suffixMin | Score | ≤ k(3)? |
|---|---|---|---|---|
| 0 | 5 | 0 | 5 | No |
| 1 | 5 | 0 | 5 | No |
| 2 | 5 | 1 | 4 | No |
| 3 | 5 | 4 | 1 | Yes! |
7. Think Like a Programmer
What do I know? For any index, I need "max of everything up to here" and "min of everything from here onward." What do I need to find? The smallest index where the difference of these two is small enough. What can I try? The most direct idea: for each index INLINECODE68, separately scan INLINECODE69 for the max and separately scan INLINECODE70 for the min, then compare. This works, but redoes a lot of scanning repeatedly for every INLINECODE71. What happens if I try every possibility? For each of the INLINECODE72 indices, scanning up to INLINECODE73 elements twice (once for the max part, once for the min part) costs about INLINECODE74 per index, so INLINECODE75 total. With INLINECODE76 only up to INLINECODE77 here, this is actually totally fine performance-wise — but it's still wasteful, and understanding the smarter way matters for building good habits (and for when INLINECODE78 is much bigger in similar problems). Can I make it faster? Yes — notice that "max of INLINECODE79" only ever changes by possibly growing as INLINECODE80 increases (each step, we just compare the new element to the previous max-so-far, we never need to rescan). Similarly, "min of INLINECODE81" only changes as INLINECODE82 decreases (walking right to left, comparing to the previous min-so-far in that direction). This means we can compute all prefix maxes in a single left-to-right pass, and all suffix mins in a single right-to-left pass — each index's answer becomes an O(1) lookup after that. What information should I remember? Two full helper arrays (INLINECODE83, INLINECODE84), each built with a single running "best so far" variable during its own pass. What pattern do I notice? This is a classic prefix/suffix precomputation pattern: whenever you need "some aggregate over everything to the left" and/or "some aggregate over everything to the right," for every position, build those aggregates once in a single pass each, rather than recomputing them from scratch per position.
8. Start With the Brute Force Solution
Brute force idea: For each index INLINECODE85 from 0 to INLINECODE86, scan INLINECODE87 to find the max, scan INLINECODE88 to find the min, compute the difference, and check against INLINECODE89. Return the first INLINECODE90 that qualifies.
Why it works: It directly computes exactly what the problem defines, for every index, with no shortcuts — guaranteed correct.
Time complexity: For each of the INLINECODE91 indices, we do up to INLINECODE92 work scanning both halves, so INLINECODE93 total.
Space complexity: INLINECODE94 extra (just a couple of tracking variables per index, no persistent extra array needed).
CODEBLOCK1
9. Explain the Brute Force Code Line by Line
INLINECODE95 — total number of elements. The outer INLINECODE96 loop — tries every index in order, from smallest to largest (so the very first one that qualifies is naturally the smallest stable index). INLINECODE97 — start impossibly small, so any real value we compare against it will correctly update it. The inner INLINECODE98 loop — scans every index from INLINECODE99 up to and including INLINECODE100, updating INLINECODE101 to be the running biggest value seen. This directly computes INLINECODE102. INLINECODE103 — start impossibly large, so it will correctly shrink down to the true minimum as we scan. The inner INLINECODE104 loop — scans every index from INLINECODE105 to the end, updating INLINECODE106 to the running smallest value. This computes INLINECODE107. INLINECODE108 — check the stability condition; if satisfied, we've found our answer, so return immediately. INLINECODE109 — if we finish the outer loop without ever returning, no index was stable.
10. Why Might the Brute Force Not Be Ideal (in general)?
For this specific problem, INLINECODE110 is capped at just INLINECODE111, so INLINECODE112 is at most INLINECODE113 operations — genuinely no performance problem at all here. But imagine a similar problem where INLINECODE114 could be INLINECODE115 — then INLINECODE116 would balloon to INLINECODE117 billion operations, far too slow. It's worth learning the faster technique now, both because it's cleaner code and because it's the right habit for when constraints are bigger.
11. Find the Better Approach
CODEBLOCK2
⭐ Key Insight
Before the insight
It feels like finding "max of everything up to INLINECODE118" and "min of everything from INLINECODE119 onward" requires looking at a growing/shrinking chunk of the array fresh, for every single INLINECODE120.The problem
Rescanning a growing or shrinking range from scratch, for every index, repeats a huge amount of comparison work that's almost entirely redundant between consecutive indices.The insight
INLINECODE121 is just INLINECODE122 — the max up to INLINECODE123 is simply "whatever the max was one step earlier, compared with the one new element." This means we can build the entire prefix-max array with a single left-to-right sweep, carrying forward one running value. The exact same logic applies in reverse for the suffix-min array, built with a single right-to-left sweep.After the insight
Once both helper arrays exist, answering "what's the instability score at index INLINECODE124?" for every INLINECODE125 becomes an instant lookup (INLINECODE126) — no rescanning at all. The whole algorithm becomes three simple, single-direction passes.13. Dry Run the Optimized Solution
Let's dry-run Example 2: INLINECODE127.
Step 1: Build prefixMax (left to right).
| Index | Value | prefixMax |
|---|---|---|
| 0 | 3 | 3 |
| 1 | 2 | max(3,2)=3 |
| 2 | 1 | max(3,1)=3 |
Step 2: Build suffixMin (right to left).
| Index | Value | suffixMin |
|---|---|---|
| 2 | 1 | 1 |
| 1 | 2 | min(2,1)=1 |
| 0 | 3 | min(3,1)=1 |
Step 3: Scan for the first index where INLINECODE130.
| Index | prefixMax | suffixMin | Score | ≤ 1? |
|---|---|---|---|---|
| 0 | 3 | 1 | 2 | No |
| 1 | 3 | 1 | 2 | No |
| 2 | 3 | 1 | 2 | No |
14. Optimized Code
CODEBLOCK3
CODEBLOCK4
15. Explain Optimized Code Line by Line
INLINECODE132 — total element count. INLINECODE133 — a new array where INLINECODE134 will hold INLINECODE135. INLINECODE136 — the base case: with only one element (index 0) considered, the max is that element itself. The INLINECODE137 loop — for every later index, INLINECODE138: take whatever the max was one step back, compare it to the current element, and keep the bigger one. INLINECODE139 — similarly, INLINECODE140 will hold INLINECODE141. INLINECODE142 — base case: with only the last element considered, the min is just that element. The INLINECODE143 loop — walks backward from the second-to-last index down to INLINECODE144. INLINECODE145: take whatever the min was one step ahead, compare it to the current element, keep the smaller one. The final INLINECODE146 loop — scans indices in increasing order and checks INLINECODE147. The moment this is true, we return INLINECODE148 immediately (guaranteed to be the smallest such index). INLINECODE149 — if no index satisfies the condition, none is stable.16. Test With Multiple Examples
Example 1 — Normal Case
INLINECODE150 → dry-ran manually in Section 6 → Output: INLINECODE151 ✔️Example 2 — Different Case
INLINECODE152 → dry-ran in Section 13 → Output: INLINECODE153 ✔️Example 3 — Edge Case (single element)
INLINECODE154. INLINECODE155. INLINECODE156, INLINECODE157. Check index 0: INLINECODE158? Yes! → Output: INLINECODE159 ✔️17. Edge Cases
Single-element array (INLINECODE160) → both helper arrays are just the base case, index 0's score is INLINECODE161, so it's stable exactly when INLINECODE162 — which is guaranteed by constraints, so a single-element array is always stable at index 0. No stable index exists at all → the final scan finishes without returning, correctly falling through to INLINECODE163. The array is already fully sorted increasing (e.g., INLINECODE164) → at the last index, INLINECODE165 = last element, INLINECODE166 = last element, score is INLINECODE167, so the last index is always stable. The array is sorted strictly decreasing (e.g., INLINECODE168) → INLINECODE169 stays at the first element; INLINECODE170 stays at the last element throughout — every index has the same score (INLINECODE171). All elements identical → INLINECODE172 everywhere → score is always INLINECODE173 → index 0 is always stable.
18. Time Complexity
CODEBLOCK5
Why: Each of our three passes touches every element exactly once, doing constant work per element. The total work scales linearly with INLINECODE174.
19. Space Complexity
INLINECODE175 and INLINECODE176 are each full arrays of length INLINECODE177.
So extra space used is INLINECODE178.
20. Common Mistakes Beginners Make
❌ "The max range is INLINECODE179 to INLINECODE180, and the min range is INLINECODE181 to INLINECODE182 (excluding INLINECODE183 from both)." ✅ Both INLINECODE184 and INLINECODE185 include index INLINECODE186 itself.
❌ "I should rescan the whole 0..i range from scratch every time to compute the prefix max." ✅ You only need the previous prefix max value plus the current element: INLINECODE187.
❌ "I'll build the suffix min array left to right, like the prefix max." ✅ The suffix min must be built right to left, since INLINECODE188 depends on INLINECODE189.
21. How to Recognize This Pattern in Other Problems
Watch for these signal phrases:
CODEBLOCK6
Whenever a problem asks you to compute some aggregate of everything to one side for every position, think prefix array or suffix array to optimize $O(N^2)$ to $O(N)$.
22. Interview Thinking
CODEBLOCK7
23. Mini Challenge
Try these before checking the answers:
1. Why do we build the prefix max array by comparing to the previous prefix max, rather than the original array's previous element? 2. If INLINECODE190, what would INLINECODE191 and INLINECODE192 look like, and what's the instability score at every index? 3. Why is scanning left-to-right in the final step (rather than right-to-left) important for correctly returning the smallest stable index?
Answer to Mini Challenge
1. Because the prefix max needs to reflect the biggest value seen across all elements up to this point, not just a comparison with the single element right before it. 2. INLINECODE193, INLINECODE194 — every index has score INLINECODE195. Index 0 is stable, answer is INLINECODE196. 3. Scanning left to right guarantees you encounter indices in increasing order, so the very first match you find is naturally the smallest.
24. Final Revision
🧠 Problem in One Sentence
Find the smallest index where the maximum of everything to its left (inclusive) minus the minimum of everything to its right (inclusive) is at most INLINECODE197.🔑 Main Idea
Precompute a prefix-max array (left to right) and a suffix-min array (right to left), then scan once for the first index where their difference is at most INLINECODE198.⚙️ Algorithm
1. Build INLINECODE199, left to right. 2. Build INLINECODE200, right to left. 3. Scan indices left to right, returning the first INLINECODE201 where INLINECODE202. 4. If none found, return INLINECODE203.⏱️ Complexity
Time: INLINECODE204 Space: INLINECODE205🎯 Pattern to Remember
"Aggregate over everything to the left/right, for every index" → prefix/suffix precomputation, not repeated rescanning.25. Beginner Quiz
1. (Understanding) Why is index INLINECODE206 included in both the left range and the right range when computing its instability score? 2. (Basic concept) What's the difference between how you build a prefix max array versus a suffix min array — which direction does each one scan? 3. (Logic) Why is it safe to return the first index (scanning left to right) that satisfies the stability condition, without needing to check any later indices? 4. (Dry run) For INLINECODE207, build the prefix max and suffix min arrays, and find the smallest stable index (or determine there isn't one). 5. (Complexity/pattern) Why does this problem's brute force (INLINECODE208) run instantly anyway given the constraints, and what specific phrase in the problem statement ("for each index... 0 to i" and "i to n-1") should cue you to reach for prefix/suffix arrays regardless of whether the constraints strictly require it?