Watch 7 video solutions for Find Good Days to Rob the Bank, a medium level problem involving Array, Dynamic Programming, Prefix Sum. This walkthrough by Coding Decoded has 2,523 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
time days before and after the ith day,time days before i are non-increasing, andtime 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 <= 1050 <= security[i], time <= 105Problem Overview: You receive an integer array security where security[i] represents the number of guards on day i. A day is considered good if the previous time days are non-increasing and the next time days are non-decreasing. Return all indices that satisfy both conditions.
Approach 1: Two-Pass with Auxiliary Arrays (O(n) time, O(n) space)
This method scans the array twice and stores trend information in two helper arrays. The first pass builds a left array where left[i] counts how many consecutive previous days have a non-increasing guard count. The second pass builds a right array where right[i] counts consecutive next days with non-decreasing guards. After computing both arrays, iterate once more and collect indices where left[i] >= time and right[i] >= time. The key insight is precomputing monotonic streaks so each index can be validated in O(1). This approach uses simple array traversal and resembles a lightweight dynamic programming pattern because each state depends on the previous one.
Approach 2: Sliding Window with Prefix Arrays (O(n) time, O(n) space)
This variation uses prefix-style preprocessing to track monotonic violations inside windows. Instead of storing full streak lengths, compute prefix indicators showing where increasing or decreasing relationships break. With these arrays, each candidate index checks whether the window [i-time, i] has no increases and the window [i, i+time] has no decreases. Prefix sums allow constant-time validation for every index after preprocessing. This technique combines sliding window reasoning with prefix sum style counting to avoid repeated comparisons.
Recommended for interviews: The two-pass auxiliary array approach is the expected solution. It is straightforward, easy to reason about, and clearly demonstrates linear preprocessing followed by constant-time checks. A brute-force window check would take O(n * time) and shows baseline reasoning, but the O(n) preprocessing solution demonstrates stronger algorithmic thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pass with Auxiliary Arrays | O(n) | O(n) | Standard interview solution; easy to implement and reason about monotonic streaks |
| Sliding Window with Prefix Arrays | O(n) | O(n) | Useful when validating window constraints using prefix counts instead of streak arrays |