Problem statement

A bank logs how many guards are on duty each day: security[i] is the count on day i. Given an integer time, day i is a good day when:

• there are at least time days before and after it,
• the guard counts over the time days before day i never increase: security[i - time] >= … >= security[i - 1] >= security[i], and
• the guard counts over the time days after it never decrease: security[i] <= security[i + 1] <= … <= security[i + time].

Return all good days in increasing order.

Example 1

Input: security = [5,3,3,3,5,6,2], time = 2
Output: [2,3]
Explanation: Day 2: 5 >= 3 >= 3 and 3 <= 3 <= 5. Day 3: 3 >= 3 >= 3 and 3 <= 5 <= 6. No other day qualifies.

Example 2

Input: security = [1,1,1,1,1], time = 0
Output: [0,1,2,3,4]
Explanation: With `time = 0` every day is good.

Example 3

Input: security = [1,2,3,4,5,6], time = 2
Output: []
Explanation: The counts only ever rise, so no day has a non-increasing stretch before it.

Constraints

• 1 <= security.length <= 10^5
• 0 <= security[i], time <= 10^5

Hints for Find Good Days to Rob the Bank

1. Hint 1

   Checking 2 * time neighbours for every day is too slow. Can you know, for each day, how long the non-increasing stretch ending there is?

2. Hint 2

   Let before[i] be the number of consecutive steps ending at i with security[j - 1] >= security[j], and after[i] the number of consecutive steps starting at i with security[j] <= security[j + 1]. Both are one linear pass.

3. Hint 3

   Day i is good exactly when before[i] >= time and after[i] >= time.

How to solve Find Good Days to Rob the Bank

Precompute, for every day, how far the non-increasing run reaches back and how far the non-decreasing run reaches forward. A day is good when both reach at least time steps.

Approach

1. before[0] = 0; for i >= 1, before[i] = before[i - 1] + 1 if security[i - 1] >= security[i], else 0.
2. after[n - 1] = 0; for i <= n - 2 from right to left, after[i] = after[i + 1] + 1 if security[i] <= security[i + 1], else 0.
3. Collect every i (in increasing order) with before[i] >= time and after[i] >= time.

Why it works

before[i] counts the longest run of non-increasing steps ending at i, so the time days before i are non-increasing iff before[i] >= time — which also guarantees i >= time. Symmetrically for after[i], which also guarantees i + time <= n - 1.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• The conditions are non-strict: equal guard counts are allowed on both sides.
• With time = 0 every day qualifies — before[i] >= 0 always holds.

Reference solution

Python

from typing import List

def goodDaysToRobBank(security: List[int], time: int) -> List[int]:
    n = len(security)
    before = [0] * n
    after = [0] * n
    for i in range(1, n):
        if security[i - 1] >= security[i]:
            before[i] = before[i - 1] + 1
    for i in range(n - 2, -1, -1):
        if security[i] <= security[i + 1]:
            after[i] = after[i + 1] + 1
    return [i for i in range(n) if before[i] >= time and after[i] >= time]

Java

public static int[] goodDaysToRobBank(int[] security, int time) {
    int n = security.length;
    int[] before = new int[n], after = new int[n];
    for (int i = 1; i < n; i++) before[i] = security[i - 1] >= security[i] ? before[i - 1] + 1 : 0;
    for (int i = n - 2; i >= 0; i--) after[i] = security[i] <= security[i + 1] ? after[i + 1] + 1 : 0;
    List<Integer> out = new ArrayList<>();
    for (int i = 0; i < n; i++) if (before[i] >= time && after[i] >= time) out.add(i);
    int[] res = new int[out.size()];
    for (int i = 0; i < res.length; i++) res[i] = out.get(i);
    return res;
}

C++

vector<int> goodDaysToRobBank(vector<int>& security, int time) {
    int n = security.size();
    vector<int> before(n, 0), after(n, 0), out;
    for (int i = 1; i < n; i++) before[i] = security[i - 1] >= security[i] ? before[i - 1] + 1 : 0;
    for (int i = n - 2; i >= 0; i--) after[i] = security[i] <= security[i + 1] ? after[i + 1] + 1 : 0;
    for (int i = 0; i < n; i++) if (before[i] >= time && after[i] >= time) out.push_back(i);
    return out;
}

JavaScript

var goodDaysToRobBank = function(security, time) {
    var n = security.length;
    var before = new Array(n), after = new Array(n);
    before[0] = 0;
    for (var i = 1; i < n; i++) before[i] = security[i - 1] >= security[i] ? before[i - 1] + 1 : 0;
    after[n - 1] = 0;
    for (var j = n - 2; j >= 0; j--) after[j] = security[j] <= security[j + 1] ? after[j + 1] + 1 : 0;
    var out = [];
    for (var k = 0; k < n; k++) if (before[k] >= time && after[k] >= time) out.push(k);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium