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.
This approach involves creating two auxiliary arrays to track the length of contiguous, non-increasing, and non-decreasing subsequences for each day. After populating these arrays, iterate over the days to find the 'good' days that satisfy the conditions for the specified time.
This solution uses two auxiliary arrays 'left' and 'right' to track the length of non-increasing and non-decreasing sequences respectively. We first fill these arrays in two separate passes—one from left to right and one from right to left. Afterward, we iterate over each day from 'time' to 'size-time' and check if both the 'left' and 'right' arrays at that position are greater than or equal to 'time' to determine a 'good' day.
Time Complexity: O(n) — where n is the number of days in the 'security' array as we are iterating over the array a few times.
Space Complexity: O(n) — for storing the 'left' and 'right' auxiliary arrays.
This approach uses prefix arrays to directly compare elements instead of recalculating subsequences, cutting down redundant operations. Essentially, prefix arrays effectively determine which days are optimal for conducting the robbery by focusing on iterative evaluations through windowed checks.
This approach leverages prefix arrays to minimize redundant calculations when determining the suitability of each day. Prefix arrays succinctly encapsulate increasing or decreasing sequences up to each index, thus resulting in faster O(n) checking by directly using sum comparisons within the windowed constraints.
Python
JavaScript
Time Complexity: O(n).
Space Complexity: O(n).
| Approach | Complexity |
|---|---|
| Two-Pass Approach with Auxiliary Arrays | Time Complexity: O(n) — where n is the number of days in the 'security' array as we are iterating over the array a few times. |
| Sliding Window with Prefix Arrays | Time Complexity: O(n). |
| Default Approach | — |
| 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 |
Find Good Days to Rob the Bank | Leetcode 2100 | Live coding session 🔥🔥🔥 | Linear approach • Coding Decoded • 2,523 views views
Watch 6 more video solutions →Practice Find Good Days to Rob the Bank with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor