3904. Smallest Stable Index II

Good news: this is exactly the same problem as Part I — same definition, same examples — with only one thing changed in the constraints: INLINECODE0 can now be up to INLINECODE1 instead of INLINECODE2. That single change is the whole story of this "sequel." Let's walk through it properly anyway, since it's worth understanding why this constraint bump matters.

---

1. Problem in Very Simple Language

Identical to Part I: for every index INLINECODE3, the instability score is INLINECODE4 — the biggest value from the start through INLINECODE5 (inclusive), minus the smallest value from INLINECODE6 through the end (inclusive). An index is stable if this score is INLINECODE7. Find the smallest stable index, or INLINECODE8 if none exists.

What's given: INLINECODE9, INLINECODE10 — but now INLINECODE11 can have up to 100,000 elements. What to find: the same thing as before. What to return: the same thing as before.

---

2. Real-Life Analogy

Same hiking-trail analogy as Part I: standing at any point, you look backward for the highest peak you've passed, and forward for the lowest valley ahead. You want the first spot where that gap is small enough. The only difference now: the trail is 1,000 times longer — so whatever method you use to scan it needs to not get dramatically slower just because the trail grew.

---

3. Important Programming Concepts I Need First

Everything from Part I still applies directly:

Prefix Max — INLINECODE12, built in one left-to-right pass, where INLINECODE13. Suffix Min — INLINECODE14, built in one right-to-left pass, where INLINECODE15. Why these avoid rescanning: each one only ever needs "the previous running best" plus "the one new element," never a fresh look back over the whole range.

New concept this time: Why constraints actually matter here

Concept: A brute-force approach with nested loops (INLINECODE16) that seemed "fine" when INLINECODE17 (at most INLINECODE18 operations) becomes catastrophic when INLINECODE19 (up to INLINECODE20 operations) — the exact same code, just given a bigger input, goes from "instant" to "would take minutes or longer," which competitive judges like LeetCode simply won't wait for (they enforce a time limit, typically a couple of seconds). Why we need it: This is precisely why Part I could get away with brute force but Part II cannot — the algorithm must be genuinely INLINECODE21 (or close to it) this time, not just "technically correct."

---

4. Understand the Input

Identical to Part I's Example 1: CODEBLOCK0

---

5. Understand the Output

Identical reasoning to Part I: output is INLINECODE22, since index 3 is the first index where INLINECODE23.

---

6. Solve the Example Manually

This is identical to Part I's Section 6 — building INLINECODE24 and INLINECODE25, then finding index INLINECODE26 as the first place where INLINECODE27. Nothing changes about the manual process — only about how we'd have to implement it if INLINECODE28 were huge.

---

7. Think Like a Programmer

What do I know? The exact same relationships as Part I: INLINECODE29, and INLINECODE30. What's different this time? With INLINECODE31 up to INLINECODE32, any approach that does INLINECODE33 work per index (like rescanning a growing/shrinking range from scratch for every INLINECODE34) totals INLINECODE35 ≈ INLINECODE36 billion operations in the worst case — this will time out. What must I do instead? Use the prefix-max / suffix-min precomputation from Part I — which was already the "proper" INLINECODE37 solution there, just not strictly required by Part I's tiny constraints. Now, it's mandatory. Is there anything conceptually new to figure out? No — the insight is 100% the same as Part I. This "Part II" is really testing whether you actually understood why the optimized approach works, or whether you just happened to get away with brute force last time because the input was small.

---

8. Why the Part I Brute Force Now Fails

Let's revisit the brute force from Part I to see exactly where it breaks:

CODEBLOCK1

Why it times out: The outer loop runs INLINECODE38 times, and each iteration does up to INLINECODE39 work (rescanning both the left part and the right part from scratch). That's INLINECODE40 total — for INLINECODE41, that's on the order of INLINECODE42 billion basic operations. Even at a very generous "100 million operations per second" estimate, that's roughly 100 seconds — far beyond what any judge will allow (typically 1-2 seconds for Java).

---

11. The Fix: Reuse Part I's Optimized Approach

CODEBLOCK2

---

⭐ Key Insight

Before the insight

It's tempting to think "Part II is a totally new, harder problem" just because the constraints grew.

The problem

Nothing about the definition changed — only the scale. If you don't already have a truly INLINECODE43 (or INLINECODE44) solution, the bigger input size will expose that weakness immediately via a timeout, even though your Part I brute-force logic was 100% correct.

The insight

Constraint changes between "Part I" and "Part II" versions of a problem are almost always a direct signal about required time complexity, not a signal that the core logic needs to change. The prefix-max / suffix-min technique from Part I was already the right full solution — Part I just didn't force you to discover it. Part II does.

After the insight

We reuse the exact same algorithm, unchanged in structure, and it now comfortably handles the full constraint range.

---

13. Dry Run

Identical to Part I's Section 13 (Example 2: INLINECODE45 → INLINECODE46, INLINECODE47, every index scores INLINECODE48, none INLINECODE49 → INLINECODE50). The computation process is completely unchanged; only the size of array this process needs to comfortably scale to has grown.

---

14. Optimized Code

CODEBLOCK3

CODEBLOCK4

---

16. Test With Multiple Examples

Example 1 — Normal Case

INLINECODE51 → Output: INLINECODE52 ✔️

Example 2 — Different Case

INLINECODE53 → Output: INLINECODE54 ✔️

Example 3 — Edge Case

INLINECODE55 → Output: INLINECODE56 ✔️

Example 4 — The case that actually distinguishes Part I from Part II

A worst-case-shaped array of length INLINECODE57, e.g. strictly decreasing (INLINECODE58), with a generous INLINECODE59. The brute force from Section 8 would take on the order of 10 billion operations and time out. The prefix/suffix version processes this instantly, doing three clean passes of INLINECODE60 steps each — about INLINECODE61 total operations, finishing in a few milliseconds.

---

17. Edge Cases

All the same edge cases from Part I apply unchanged (single element, all-increasing, all-decreasing, all-equal, no stable index). One new thing worth calling out explicitly for this version:

Maximum-size input (INLINECODE62) combined with an unlucky shape (e.g., no stable index exists at all, forcing a full scan through all 100,000 indices before returning INLINECODE63) — this is the true stress test. Our INLINECODE64 solution handles it easily (three INLINECODE65-length passes); the brute force from Section 8 would not.

---

18. Time Complexity

CODEBLOCK5

Why this matters now, when it didn't in Part I: with INLINECODE66, INLINECODE67 tops out at INLINECODE68 operations — trivially fast regardless of approach. With INLINECODE69, INLINECODE70 explodes to INLINECODE71 billion — a difference of roughly a million-fold increase in work, purely from the constraint change. This is exactly why "Part II" versions of easy problems exist: to force you to actually use the efficient technique, not just the correct-but-slow one.

---

19. Space Complexity

Same as Part I: INLINECODE72, for the two helper arrays INLINECODE73 and INLINECODE74. This is very comfortable even at INLINECODE75 (two arrays of 100,000 integers each is trivial memory usage).

---

20. Common Mistakes Beginners Make

❌ "My Part I brute-force solution worked, so it must still be correct here — maybe there's a bug elsewhere." ✅ The logic is correct, but too slow. A "Time Limit Exceeded" verdict (rather than "Wrong Answer") is the classic symptom of an algorithm that's logically right but complexity-wise inadequate for the given constraints — the fix is a faster algorithm, not different logic.

❌ "I'll just try to make the brute force's inner loops slightly faster (micro-optimizing the same O(n²) shape)." ✅ Shaving constants off an INLINECODE76 algorithm doesn't change the fundamental scaling problem — at INLINECODE77, even a "twice as fast" INLINECODE78 solution is still on the order of 5 billion operations, still far too slow. You need to change the complexity class entirely (to INLINECODE79), not just optimize within the slow one.

❌ "This must require a totally different, more advanced algorithm since it's now rated differently or has bigger constraints." ✅ Not necessarily — sometimes (like here), the correct efficient algorithm was already fully knowable from the original problem statement; the bigger constraints just remove the option of skipping it.

---

21. How to Recognize This Pattern in Other Problems

CODEBLOCK6

Whenever you see a "II" sequel with the exact same wording but drastically bigger limits, your first move should be: re-examine your Part I solution's complexity, and if it wasn't already O(n) or O(n log n), figure out the version of it that is.

---

22. Interview Thinking

CODEBLOCK7

The interview lesson here: always ask yourself, even when brute force technically passes, "would this still work if the input were 1,000x bigger?" — that habit is exactly what separates a solution that happens to pass small tests from one that's genuinely correct in complexity.

---

23. Mini Challenge

1. If INLINECODE80 and the array happens to be sorted in strictly increasing order, roughly how many operations would the Part I brute force perform in the worst case (as it checks index by index)? Roughly how many would the optimized version perform? 2. Why doesn't building INLINECODE81 and INLINECODE82 as two separate* INLINECODE83 passes (rather than one combined pass) hurt our overall complexity? 3. If a future "Part III" of this problem allowed INLINECODE84 up to INLINECODE85, would the current INLINECODE86 solution still likely be fast enough? Why?

Answer to Mini Challenge

1. Brute force: roughly INLINECODE87 billion operations in the worst case. Optimized: roughly INLINECODE88 operations total (one pass each for prefixMax, suffixMin, and the final scan) — a difference of about four orders of magnitude. 2. Because INLINECODE89 is still INLINECODE90 overall — adding a fixed number of linear passes together doesn't change the overall growth rate; it's still "grows proportionally to n," just with a bigger constant multiplier (3x instead of 1x). 3. Very likely yes — INLINECODE91 with INLINECODE92 is about 10 million basic operations across each pass (30 million total), which modern judges can typically handle within a couple of seconds.

---

24. Final Revision

🧠 Problem in One Sentence

Identical to Part I: find the smallest index where the max of everything to its left (inclusive) minus the min of everything to its right (inclusive) is at most INLINECODE93 — but now INLINECODE94 can be up to INLINECODE95, so the solution must genuinely be INLINECODE96.

🔑 Main Idea

The Part I "optimized" approach (prefix-max + suffix-min precomputation) wasn't optional flourish — it's the mandatory solution once INLINECODE97 grows large, since the brute-force INLINECODE98 rescanning approach becomes computationally infeasible.

⚙️ Algorithm

1. Build INLINECODE99, left to right. 2. Build INLINECODE100, right to left. 3. Scan left to right, return the first INLINECODE101 where INLINECODE102. 4. If none found, return INLINECODE103.

⏱️ Complexity

Time: INLINECODE104 Space: INLINECODE105

🎯 Pattern to Remember

When a "Part II" keeps the same definition but massively raises INLINECODE106, treat it as a direct instruction: your solution must be O(n) or O(n log n) — go find (or reuse) that version.

---

25. Beginner Quiz

1. (Understanding) What is the only thing that actually changed between Part I and Part II of this problem? 2. (Basic concept) Roughly how many operations does an INLINECODE107 algorithm perform when INLINECODE108, and how does that compare to an INLINECODE109 algorithm on the same input? 3. (Logic) Why does a solution that passes all of Part I's test cases not guarantee it will pass Part II's, even though the problem statement is word-for-word identical? 4. (Dry run) For a strictly decreasing array of length 5, INLINECODE110, with INLINECODE111, compute INLINECODE112, INLINECODE113, and find the smallest stable index using the optimized approach. 5. (Complexity/pattern) What general lesson should you take away for recognizing "Part II" style sequels on LeetCode, specifically regarding how much attention to pay to the constraints section versus the problem description?