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 ofall days (0-indexed) that are good days to rob the bank.The order that the days are returned in does****not matter.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3
4

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

1
2
3
4
5

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 <= 10^5
  • 0 <= security[i], time <= 10^5

Solution

Method 1 - Naive

A brute-force solution would check every potential day i and then, for each one, loop time days backward and time days forward. This is inefficient because the checks for adjacent days (e.g., i and i+1) overlap significantly.

Method 1 - Prefix Sum

A better approach is to precompute the necessary information. We can determine if a day i is a good day by answering two questions:

  1. How many consecutive days ending at i have non-increasing guards?
  2. How many consecutive days starting at i have non-decreasing guards?

We can answer these questions for all days in linear time using two auxiliary arrays:

  1. pre array: pre[i] will store the number of consecutive days ending at i (inclusive) that satisfy the non-increasing condition. We can compute this with a single pass from left to right.

    • pre[i] = pre[i-1] + 1 if sec[i-1] >= sec[i].
    • Otherwise, the streak is broken, so pre[i] is reset to 0.

  2. suf array: suf[i] will store the number of consecutive days starting at i (inclusive) that satisfy the non-decreasing condition. We compute this with a single pass from right to left.

    • suf[i] = suf[i+1] + 1 if sec[i] <= sec[i+1].
    • Otherwise, the streak is broken, so suf[i] is reset to 0.

After populating pre and suf, we can make a final pass. A day i is a “good day” if it has at least time days before and after it, and both conditions are met. This translates to checking if pre[i] >= time and suf[i] >= time for all i in the valid range [time, n - time).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

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

class Solution {
    /**
     * Finds all "good" days to rob the bank.
     *
     * @param sec The daily number of guards.
     * @param time The number of days for the security check.
     * @return A list of indices of the good days.
     */
    public List<Integer> goodDaysToRobBank(int[] sec, int time) {
        int n = sec.length;
        // pre[i]: number of consecutive non-increasing days ending at i
        int[] pre = new int[n];
        for (int i = 1; i < n; i++) {
            if (sec[i - 1] >= sec[i]) {
                pre[i] = pre[i - 1] + 1;
            }
        }

        // suf[i]: number of consecutive non-decreasing days starting at i
        int[] suf = new int[n];
        for (int i = n - 2; i >= 0; i--) {
            if (sec[i] <= sec[i + 1]) {
                suf[i] = suf[i + 1] + 1;
            }
        }

        List<Integer> ans = new ArrayList<>();
        // A day `i` is good if it has `time` valid days before and after.
        for (int i = time; i < n - time; i++) {
            if (pre[i] >= time && suf[i] >= time) {
                ans.add(i);
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

from typing import List

class Solution:
    """
    Finds all "good" days to rob the bank.
    """
    def goodDaysToRobBank(self, sec: List[int], time: int) -> List[int]:
        """
        Calculates good days based on security guard patterns.

        :param sec: The daily number of guards.
        :param time: The number of days for the security check.
        :return: A list of indices of the good days.
        """
        n: int = len(sec)
        
        # pre[i]: number of consecutive non-increasing days ending at i
        pre: List[int] = [0] * n
        for i in range(1, n):
            if sec[i - 1] >= sec[i]:
                pre[i] = pre[i - 1] + 1
        
        # suf[i]: number of consecutive non-decreasing days starting at i
        suf: List[int] = [0] * n
        for i in range(n - 2, -1, -1):
            if sec[i] <= sec[i + 1]:
                suf[i] = suf[i + 1] + 1
                
        ans: List[int] = []
        # A day `i` is good if it has `time` valid days before and after.
        for i in range(time, n - time):
            if pre[i] >= time and suf[i] >= time:
                ans.append(i)
                
        return ans

Complexity

  • ⏰ Time complexity: O(n). We make three separate passes through the array: one to compute pre, one for suf, and one to find the answer. Each pass takes O(n) time.
  • 🧺 Space complexity: O(n). We use two additional arrays, pre and suf, each of size n, to store our precomputed values.