Find good days to rob the bank

Array Dynamic Programming Prefix Sum

51.4% acceptance

Feb 25, 2026

1000

You and a gang of thieves are planning on robbing a bank. You are given a 0-indexed integer array security, where security[i] is the number of guards on duty on the ith day. The days are numbered starting from 0. You are also given an integer time. The ith day is a good day to rob the bank if: There are at least time days before and after the ith day, The number of guards at the bank for the time days before i are non-increasing, and The number of guards at the bank for the time days after i are non-decreasing. More formally, day i is a good day if security[i-time] >= ... >= security[i] <= ... <= security[i+time]. Return a list of all days (0-indexed) that are good days to rob the bank.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn good_days_to_rob_bank(security: Vec<i32>, time: i32) -> Vec<i32> {
    let n = security.len();
    let time = time as usize;

    // dec[i] = number of consecutive non-increasing days ending at i (from left)
    let mut dec = vec![0usize; n];
    for i in 1..n {
      if security[i] <= security[i - 1] {
        dec[i] = dec[i - 1] + 1;
      }
    }

    // inc[i] = number of consecutive non-decreasing days starting at i (from right)
    let mut inc = vec![0usize; n];
    for i in (0..n - 1).rev() {
      if security[i] <= security[i + 1] {
        inc[i] = inc[i + 1] + 1;
      }
    }

    let mut result = Vec::new();
    let end = n.saturating_sub(time);
    for i in time..end {
      if dec[i] >= time && inc[i] >= time {
        result.push(i as i32);
      }
    }
    result
  }
}