DDSA Solutions

3904. Smallest Stable Index II

EasyView on LeetCode
ArrayPrefix Sum

Problem Overview

This is the same stability rule as part I, but arrays can be much longer.

Intuition

This is the same stability rule as part I, but arrays can be much longer. The score at i still depends only on the prefix maximum and the suffix minimum that both include i. Precompute suffix minima once, then scan forward with a running max.

Algorithm

  1. 1Build right[i] = min(nums[i], nums[i+1], ..., nums[n-1]) from the back.
  2. 2Walk i from 0 to n-1 with leftMax = max(nums[0..i]).
  3. 3If leftMax - right[i] <= k, return i immediately.
  4. 4If the scan finishes with no hit, return -1.

Example Walkthrough

Input: nums = [3, 2, 1], k = 1

  1. 1.Suffix mins are [1, 1, 1].
  2. 2.Every index has score 3 - 1 = 2.
  3. 3.2 is greater than k, so no stable index exists.

Output: -1

Common Pitfalls

  • •Same formula as 3903; only the input size limit changes.
  • •Use O(n) suffix storage. Recomputing suffix min per index would be O(n^2).
  • •leftMax must include nums[i] before comparing to right[i].
  • •Return the first qualifying index, not the last.
3904.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