Find Good Days to Rob the Bank

Med

#1912Time: 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.

Patterns

Dynamic Programming Prefix Sum

Data structures

Array

Prompt

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^th day. The days are numbered starting from 0. You are also given an integer time.

The i^th day is a good day to rob the bank if:

There are at least time days before and after the i^th 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 <= 10⁵
0 <= security[i], time <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

For each candidate day i, we perform two separate checks:

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.
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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<Integer> goodDaysToRobBank(int[] security, int time) {6        List<Integer> goodDays = new ArrayList<>();7        int n = security.length;8 9        // Iterate through all possible good days10        for (int i = time; i < n - time; i++) {11            boolean nonIncreasingBefore = true;12            // Check for non-increasing sequence of 'time' days before day i13            for (int j = 1; j <= time; j++) {14                if (security[i - j] < security[i - j + 1]) {15                    nonIncreasingBefore = false;16                    break;17                }18            }19 20            if (nonIncreasingBefore) {21                boolean nonDecreasingAfter = true;22                // Check for non-decreasing sequence of 'time' days after day i23                for (int j = 1; j <= time; j++) {24                    if (security[i + j - 1] > security[i + j]) {25                        nonDecreasingAfter = false;26                        break;27                    }28                }29                if (nonDecreasingAfter) {30                    goodDays.add(i);31                }32            }33        }34        return goodDays;35    }36}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

We define two DP arrays:

nonIncreasing[i]: Stores the length of the continuous non-increasing subarray of security ending at index i.
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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public List<Integer> goodDaysToRobBank(int[] security, int time) {6        int n = security.length;7        int[] nonIncreasing = new int[n];8        int[] nonDecreasing = new int[n];9 10        // Calculate length of non-increasing subarray ending at i11        nonIncreasing[0] = 1;12        for (int i = 1; i < n; i++) {13            if (security[i - 1] >= security[i]) {14                nonIncreasing[i] = nonIncreasing[i - 1] + 1;15            } else {16                nonIncreasing[i] = 1;17            }18        }19 20        // Calculate length of non-decreasing subarray starting at i21        nonDecreasing[n - 1] = 1;22        for (int i = n - 2; i >= 0; i--) {23            if (security[i] <= security[i + 1]) {24                nonDecreasing[i] = nonDecreasing[i + 1] + 1;25            } else {26                nonDecreasing[i] = 1;27            }28        }29 30        List<Integer> goodDays = new ArrayList<>();31        // A day i is good if there are 'time' days before and after32        // and the conditions are met.33        for (int i = time; i < n - time; i++) {34            // The non-increasing part has length time+1 (from i-time to i)35            // The non-decreasing part has length time+1 (from i to i+time)36            if (nonIncreasing[i] >= time + 1 && nonDecreasing[i] >= time + 1) {37                goodDays.add(i);38            }39        }40 41        return goodDays;42    }43}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2public3  List<Integer> goodDaysToRobBank(int[] security, int time) {4    int n = security.length;5    if (n <= time * 2) {6      return Collections.emptyList();7    }8    int[] left = new int[n];9    int[] right = new int[n];10    for (int i = 1; i < n; ++i) {11      if (security[i] <= security[i - 1]) {12        left[i] = left[i - 1] + 1;13      }14    }15    for (int i = n - 2; i >= 0; --i) {16      if (security[i] <= security[i + 1]) {17        right[i] = right[i + 1] + 1;18      }19    }20    List<Integer> ans = new ArrayList<>();21    for (int i = time; i < n - time; ++i) {22      if (time <= Math.min(left[i], right[i])) {23        ans.add(i);24      }25    }26    return ans;27  }28}

1class Solution {2public:3  vector<int> goodDaysToRobBank(vector<int> &security, int time) {4    int n = security.size();5    if (n <= time * 2)6      return {};7    vector<int> left(n);8    vector<int> right(n);9    for (int i = 1; i < n; ++i)10      if (security[i] <= security[i - 1])11        left[i] = left[i - 1] + 1;12    for (int i = n - 2; i >= 0; --i)13      if (security[i] <= security[i + 1])14        right[i] = right[i + 1] + 1;15    vector<int> ans;16    for (int i = time; i < n - time; ++i)17      if (time <= min(left[i], right[i]))18        ans.push_back(i);19    return ans;20  }21};

1class Solution:2    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])]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem