Find all good indices

Array Dynamic Programming Prefix Sum

40.7% acceptance

Feb 25, 2026

673

You are given a 0-indexed integer array nums of size n and a positive integer k. We call an index i in the range k <= i < n - k good if the following conditions are satisfied: The k elements that are just before the index i are in non-increasing order. The k elements that are just after the index i are in non-decreasing order. Return an array of all good indices sorted in increasing order.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn good_indices(nums: Vec<i32>, k: i32) -> Vec<i32> {
    let n = nums.len();
    let k = k as usize;
    // dec[i] = length of non-increasing run ending at i
    let mut dec = vec![1usize; n];
    // inc[i] = length of non-decreasing run starting at i
    let mut inc = vec![1usize; n];

    for i in 1..n {
      if nums[i] <= nums[i - 1] {
        dec[i] = dec[i - 1] + 1;
      }
    }
    for i in (0..n - 1).rev() {
      if nums[i] <= nums[i + 1] {
        inc[i] = inc[i + 1] + 1;
      }
    }

    let mut ans = vec![];
    for i in k..n - k {
      if dec[i - 1] >= k && inc[i + 1] >= k {
        ans.push(i as i32);
      }
    }
    ans
  }
}