# Find Good Days to Rob the Bank
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-good-days-to-rob-the-bank)
Canonical: https://scaleengineer.com/dsa/problems/find-good-days-to-rob-the-bank
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## Problem
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, 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 = 2
**Output:** [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 = 0
**Output:** [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 = 2
**Output:** []
**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.

**Constraints:**

* `1 <= security.length <= 105`
* `0 <= security[i], time <= 105`

# Approaches
## Brute Force Iteration
This approach directly translates the problem statement into code. We iterate through each day that could potentially be a good day to rob the bank. A day `i` is a potential candidate only if there are at least `time` days before it and `time` days after it. This means we only need to check days `i` in the range `[time, n - 1 - time]`, where `n` is the total number of days.
**Time:** O(n * time). The outer loop runs for `n - 2 * time` iterations. Inside it, there are two loops, each running up to `time` times. This results in a total time complexity of `O((n - 2*time) * 2*time)`, which simplifies to `O(n * time)`. · **Space:** O(1) extra space. The space used for the output list can be up to O(n) in the worst case, but this is often excluded from space complexity analysis.
**Pros:** Simple to understand and implement as it directly follows the problem's definition.; Low space complexity if the output list is not considered.
**Cons:** Highly inefficient for large inputs, especially when `time` is large. The `O(n * time)` complexity can lead to a 'Time Limit Exceeded' error on competitive programming platforms.; It performs a lot of redundant computations. For example, when checking day `i` and day `i+1`, the check for the overlapping window of days is performed twice.
### Explanation
For each candidate day `i`, we perform two separate checks:
1.  **Non-increasing before:** We check if the number of guards is non-increasing for `time` days leading up to and including day `i`. This involves a loop from `i - time` to `i - 1`, verifying that `security[j] >= security[j+1]` for each `j`.
2.  **Non-decreasing after:** We check if the number of guards is non-decreasing for `time` days starting from day `i`. This involves another loop from `i` to `i + time - 1`, verifying that `security[j] <= security[j+1]` for each `j`.
If both conditions are satisfied, we add the day `i` to our list of good days.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> goodDaysToRobBank(int[] security, int time) {
        List<Integer> goodDays = new ArrayList<>();
        int n = security.length;

        // Iterate through all possible good days
        for (int i = time; i < n - time; i++) {
            boolean nonIncreasingBefore = true;
            // Check for non-increasing sequence of 'time' days before day i
            for (int j = 1; j <= time; j++) {
                if (security[i - j] < security[i - j + 1]) {
                    nonIncreasingBefore = false;
                    break;
                }
            }

            if (nonIncreasingBefore) {
                boolean nonDecreasingAfter = true;
                // Check for non-decreasing sequence of 'time' days after day i
                for (int j = 1; j <= time; j++) {
                    if (security[i + j - 1] > security[i + j]) {
                        nonDecreasingAfter = false;
                        break;
                    }
                }
                if (nonDecreasingAfter) {
                    goodDays.add(i);
                }
            }
        }
        return goodDays;
    }
}
```
### Algorithm
- Initialize an empty list `goodDays` to store the result.
- Let `n` be the length of the `security` array.
- Iterate through each day `i` from `time` to `n - 1 - time`. These are the only days that can have `time` days before and after them.
- For each candidate day `i`, assume it's a good day and check the two conditions:
  - **Before `i`**: Check if `security[j] >= security[j+1]` for all `j` from `i - time` up to `i - 1`. If this condition is ever violated, day `i` is not good, and we can move to the next day `i+1`.
  - **After `i`**: If the first condition holds, check if `security[j] <= security[j+1]` for all `j` from `i` up to `i + time - 1`. If this condition is violated, day `i` is not good.
- If both conditions are met for day `i`, add `i` to the `goodDays` list.
- After checking all possible days, return the `goodDays` list.

## Dynamic Programming with Precomputation
The brute-force approach is inefficient because it repeatedly checks the same subarrays. We can optimize this by pre-calculating the required properties for each day. We can use two arrays to store the lengths of consecutive non-increasing days ending at each index and consecutive non-decreasing days starting at each index. This is a classic dynamic programming technique.
**Time:** O(n). We perform three separate passes over the array: one to compute `nonIncreasing`, one for `nonDecreasing`, and a final one to find the good days. Each pass takes O(n) time, leading to a total time complexity of O(n) + O(n) + O(n) = O(n). · **Space:** O(n). We use two additional arrays, `nonIncreasing` and `nonDecreasing`, each of size `n`. The result list can also take up to O(n) space.
**Pros:** Highly efficient with a linear time complexity, making it suitable for large inputs.; The logic is clean and avoids nested loops for checking conditions, which improves performance significantly over the brute-force method.
**Cons:** Uses extra space proportional to the input size to store the two dynamic programming arrays.
### Explanation
We define two DP arrays:
1.  `nonIncreasing[i]`: Stores the length of the continuous non-increasing subarray of `security` ending at index `i`.
2.  `nonDecreasing[i]`: Stores the length of the continuous non-decreasing subarray of `security` starting at index `i`.

We can compute `nonIncreasing` with a single pass from left to right. For each `i`, if `security[i-1] >= security[i]`, the non-increasing sequence continues, so `nonIncreasing[i] = nonIncreasing[i-1] + 1`. Otherwise, a new sequence starts, so `nonIncreasing[i] = 1`.

Similarly, we can compute `nonDecreasing` with a single pass from right to left. For each `i`, if `security[i] <= security[i+1]`, the non-decreasing sequence continues, so `nonDecreasing[i] = nonDecreasing[i+1] + 1`. Otherwise, a new sequence starts, so `nonDecreasing[i] = 1`.

After pre-computing these two arrays, we can determine if a day `i` is a good day in O(1) time. A day `i` is good if:
- The `time` days before it (plus day `i`) are non-increasing. This means the length of the non-increasing subarray ending at `i` must be at least `time + 1`. So, `nonIncreasing[i] >= time + 1`.
- The `time` days after it (plus day `i`) are non-decreasing. This means the length of the non-decreasing subarray starting at `i` must be at least `time + 1`. So, `nonDecreasing[i] >= time + 1`.

We iterate from `i = time` to `n - 1 - time` and check these two conditions.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> goodDaysToRobBank(int[] security, int time) {
        int n = security.length;
        int[] nonIncreasing = new int[n];
        int[] nonDecreasing = new int[n];

        // Calculate length of non-increasing subarray ending at i
        nonIncreasing[0] = 1;
        for (int i = 1; i < n; i++) {
            if (security[i - 1] >= security[i]) {
                nonIncreasing[i] = nonIncreasing[i - 1] + 1;
            } else {
                nonIncreasing[i] = 1;
            }
        }

        // Calculate length of non-decreasing subarray starting at i
        nonDecreasing[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            if (security[i] <= security[i + 1]) {
                nonDecreasing[i] = nonDecreasing[i + 1] + 1;
            } else {
                nonDecreasing[i] = 1;
            }
        }

        List<Integer> goodDays = new ArrayList<>();
        // A day i is good if there are 'time' days before and after
        // and the conditions are met.
        for (int i = time; i < n - time; i++) {
            // The non-increasing part has length time+1 (from i-time to i)
            // The non-decreasing part has length time+1 (from i to i+time)
            if (nonIncreasing[i] >= time + 1 && nonDecreasing[i] >= time + 1) {
                goodDays.add(i);
            }
        }

        return goodDays;
    }
}
```
### Algorithm
- Let `n` be the length of the `security` array.
- Create an array `nonIncreasing` of size `n` to store the length of the non-increasing subarray ending at each index.
- Populate `nonIncreasing` by iterating from left to right. `nonIncreasing[0] = 1`. For `i > 0`, if `security[i-1] >= security[i]`, then `nonIncreasing[i] = nonIncreasing[i-1] + 1`, else `nonIncreasing[i] = 1`.
- Create an array `nonDecreasing` of size `n` to store the length of the non-decreasing subarray starting at each index.
- Populate `nonDecreasing` by iterating from right to left. `nonDecreasing[n-1] = 1`. For `i < n-1`, if `security[i] <= security[i+1]`, then `nonDecreasing[i] = nonDecreasing[i+1] + 1`, else `nonDecreasing[i] = 1`.
- Initialize an empty list `goodDays`.
- Iterate `i` from `time` to `n - 1 - time`.
- A day `i` is good if the non-increasing period ending at `i` is at least `time + 1` days and the non-decreasing period starting at `i` is also at least `time + 1` days.
- Check the condition: `nonIncreasing[i] >= time + 1` and `nonDecreasing[i] >= time + 1`. If true, add `i` to `goodDays`.
- Return `goodDays`.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> goodDaysToRobBank(int[] security, int time) {
    int n = security.length;
    if (n <= time * 2) {
      return Collections.emptyList();
    }
    int[] left = new int[n];
    int[] right = new int[n];
    for (int i = 1; i < n; ++i) {
      if (security[i] <= security[i - 1]) {
        left[i] = left[i - 1] + 1;
      }
    }
    for (int i = n - 2; i >= 0; --i) {
      if (security[i] <= security[i + 1]) {
        right[i] = right[i + 1] + 1;
      }
    }
    List<Integer> ans = new ArrayList<>();
    for (int i = time; i < n - time; ++i) {
      if (time <= Math.min(left[i], right[i])) {
        ans.add(i);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> goodDaysToRobBank(vector<int> &security, int time) {
    int n = security.size();
    if (n <= time * 2)
      return {};
    vector<int> left(n);
    vector<int> right(n);
    for (int i = 1; i < n; ++i)
      if (security[i] <= security[i - 1])
        left[i] = left[i - 1] + 1;
    for (int i = n - 2; i >= 0; --i)
      if (security[i] <= security[i + 1])
        right[i] = right[i + 1] + 1;
    vector<int> ans;
    for (int i = time; i < n - time; ++i)
      if (time <= min(left[i], right[i]))
        ans.push_back(i);
    return ans;
  }
};

```

### Python

```python
class Solution:
    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]: n = len(security) if n <= time * 2: return [] left, right = [0] * n, [0] * n for i in range(1, n): if security[i] <= security[i - 1]: left[i] = left[i - 1] + 1 for i in range(n - 2, - 1, - 1): if security[i] <= security[i + 1]: right[i] = right[i + 1] + 1 return [i for i in range(n) if time <= min(left[i], right[i])]

```