Same problem as Q1 but with larger constraints (up to 10^5). The O(n) approach with suffix min and prefix max is required.
Approach
Precompute suffix minimums. Scan left to right with a running prefix maximum. Return the first index where prefix_max - suffix_min <= k.
Time: O(n) · Space: O(n)
Code
class Solution:
def firstStableIndex(self, nums: list[int], k: int) -> int:
n = len(nums)
if n == 0:
return -1
suff_min = [0] * n
suff_min[-1] = nums[-1]
for i in range(n - 2, -1, -1):
suff_min[i] = min(suff_min[i + 1], nums[i])
current_max = -float("inf")
for i in range(n):
current_max = max(current_max, nums[i])
if current_max - suff_min[i] <= k:
return i
return -1
Interactive Trace
Step through this solution on TraceLit — set breakpoints to see exactly when the instability score drops below k.