Formatted question description: https://leetcode.ca/all/2100.html

# 2100. Find Good Days to Rob the Bank (Medium)

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 `i`

day. The days are numbered starting from ^{th}`0`

. You are also given an integer `time`

.

The `i`

day is a good day to rob the bank if:^{th}

- There are at least
`time`

days before and after the`i`

day,^{th} - 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, this means day `i`

is a good day to rob the bank if and only if `security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... <= security[i + time - 1] <= security[i + time]`

.

Return *a list of all days (0-indexed) that are good days to rob the bank*.

*The order that the days are returned in does*

**not**matter.

**Example 1:**

Input:security = [5,3,3,3,5,6,2], time = 2Output:[2,3]Explanation:On day 2, we have security[0] >= security[1] >= security[2] <= security[3] <= security[4]. On day 3, we have security[1] >= security[2] >= security[3] <= security[4] <= security[5]. No other days satisfy this condition, so days 2 and 3 are the only good days to rob the bank.

**Example 2:**

Input:security = [1,1,1,1,1], time = 0Output:[0,1,2,3,4]Explanation:Since time equals 0, every day is a good day to rob the bank, so return every day.

**Example 3:**

Input:security = [1,2,3,4,5,6], time = 2Output:[]Explanation:No day has 2 days before it that have a non-increasing number of guards. Thus, no day is a good day to rob the bank, so return an empty list.

**Example 4:**

Input:security = [1], time = 5Output:[]Explanation:No day has 5 days before and after it. Thus, no day is a good day to rob the bank, so return an empty list.

**Constraints:**

`1 <= security.length <= 10`

^{5}`0 <= security[i], time <= 10`

^{5}

**Similar Questions**:

- Non-decreasing Array (Medium)
- Longest Mountain in Array (Medium)
- Find in Mountain Array (Hard)
- Maximum Ascending Subarray Sum (Easy)

## Solution 1. Monotonic Deque

For a window `[i - time, i + time]`

, use two monotonic deques `a`

and `b`

to track the numbers in the first half `[i - time, i]`

and second half `[i, i + time]`

of the window.

Keep `a`

monotonic non-increasing and `b`

monotonic non-decreasing.

If both `a.size()`

and `b.size()`

equal `time + 1`

, we add the current index `i`

into the answer.

```
// OJ: https://leetcode.com/problems/find-good-days-to-rob-the-bank/
// Time: O(N)
// Space: O(T)
class Solution {
public:
vector<int> goodDaysToRobBank(vector<int>& A, int time) {
deque<int> a, b;
vector<int> ans;
for (int i = 0; i + time < A.size(); ++i) {
while (a.size() && A[a.back()] < A[i]) a.pop_back(); // Before pushing `i`, pop the indexes at the back of the deque whose corresponding value `< A[i]`
a.push_back(i);
if (a.front() < i - time) a.pop_front(); // Pop index if it's out of window
while (b.size() && A[b.back()] > A[i + time]) b.pop_back(); // Before pusing `i+time`, pop the indexes at the back of the deque whose corresponding value `> A[i+time]`
b.push_back(i + time);
if (b.front() < i) b.pop_front(); // Pop index if it's out of window
if (a.size() == time + 1 && b.size() == time + 1) ans.push_back(i);
}
return ans;
}
};
```

## Solution 2. DP

```
// OJ: https://leetcode.com/problems/find-good-days-to-rob-the-bank/
// Time: O(N)
// Space: O(N)
class Solution {
public:
vector<int> goodDaysToRobBank(vector<int>& A, int time) {
int N = A.size(), left = 1;
vector<int> right(N, 1), ans;
for (int i = N - 2; i >= 0; --i) {
if (A[i] <= A[i + 1]) right[i] += right[i + 1];
}
for (int i = 0; i + time < N; ++i) {
if (i - 1 >= 0 && A[i] <= A[i - 1]) left++;
else left = 1;
if (left > time && right[i] > time) ans.push_back(i);
}
return ans;
}
};
```