Smallest stable index i

Array Prefix Sum

68.3% acceptance

May 13, 2026

You are given an integer array nums of length n and an integer k. For each index i, define its instability score as max(nums[0..i]) - min(nums[i..n - 1]). In other words: max(nums[0..i]) is the largest value among the elements from index 0 to index i. min(nums[i..n - 1]) is the smallest value among the elements from index i to index n - 1. An index i is called stable if its instability score is less than or equal to k. Return the smallest stable index. If no such index exists, return -1.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn first_stable_index(nums: Vec<i32>, k: i32) -> i32 {
    let n = nums.len();
    let mut suffix_min = vec![i32::MAX; n + 1];
    for i in (0..n).rev() {
      suffix_min[i] = suffix_min[i + 1].min(nums[i]);
    }
    let mut cur_max = i32::MIN;
    for i in 0..n {
      cur_max = cur_max.max(nums[i]);
      if cur_max - suffix_min[i] <= k {
        return i as i32;
      }
    }
    -1
  }
}