DDSA Solutions

3903. Smallest Stable Index I

EasyView on LeetCode
ArrayPrefix Sum

Problem Overview

Stability at index i compares the tallest value on the left closed segment with the shortest value on the right closed segment.

Intuition

Stability at index i compares the tallest value on the left closed segment with the shortest value on the right closed segment. Precompute every suffix minimum once, then walk left to right with a running maximum. The first place where that gap is at most k is the answer.

Algorithm

  1. 1Build right[i] = min(nums[i], nums[i+1], ..., nums[n-1]) from the back.
  2. 2Initialize leftMax = 0.
  3. 3For i from 0 to n-1, set leftMax = max(leftMax, nums[i]).
  4. 4If leftMax - right[i] <= k, return i.
  5. 5If no index works, return -1.

Example Walkthrough

Input: nums = [5, 0, 1, 4], k = 3

  1. 1.Suffix mins: [0, 0, 1, 4].
  2. 2.i = 0,1,2 give scores 5, 5, 4, all above 3.
  3. 3.i = 3 gives 5 - 4 = 1, which is at most 3.

Output: 3

Common Pitfalls

  • •Both sides include index i, so use suffix min at i, not at i+1.
  • •Return the smallest index, so stop at the first success while scanning left to right.
  • •If every score exceeds k, return -1.
  • •n can be 1: score is always 0 and index 0 is stable when k >= 0.
3903.cs
C#
// Approach: Instability at i is prefix max through i minus suffix min from i.
// Precompute suffix minima, then scan left to right with a running max and
// return the first index whose score is at most k.
// Complexity: O(n) time and O(n) extra space.
public class Solution
{
    public int FirstStableIndex(int[] nums, int k)
    {
        int n = nums.Length;
        int[] right = new int[n];
        right[n - 1] = nums[n - 1];

        for (int i = n - 2; i >= 0; i--)
            right[i] = Math.Min(right[i + 1], nums[i]);

        int left = 0;
        for (int i = 0; i < n; i++)
        {
            left = Math.Max(left, nums[i]);
            if (left - right[i] <= k)
                return i;
        }
        return -1;
    }
}
Was this solution helpful?

Related Problems