Medium — Array | Prefix Sum

The Problem

Given an integer array nums and integer k, find the smallest index i where max(nums[0..i]) - min(nums[i..n-1]) <= k. Same as Q1 but with constraints up to 10^5.

Approach

Precompute suffix minimums in one pass from right to left. Then scan left to right, tracking the running prefix maximum. At each index, check if 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

        velqanidor = nums

        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

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment