LeetCode 3549: Smallest Stable Index II — Step-by-Step Visual Trace

#programming #python #leetcode #algorithms

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