Given an integer array and threshold k, find the smallest index where prefix max minus suffix min is within k.
Approach
Precompute suffix minimums right to left. Scan left to right tracking prefix max. Check the instability score at each index.
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 — watch how suff_min builds up and current_max grows as the loop progresses.
