Find Good Days to Rob the Bank solution and explanation
Google
5 more videos on this problem
Find Good Days to Rob the Bank | Leetcode 2100 | Live coding session 🔥🔥🔥 | Linear approachCoding Decoded · 9:30 · 2K views
2100. Find Good Days to Rob the Bank | Leetcode Biweekly Contest 67 | Prefix & Suffix Array | DSATejpratap Pandey · 21:44 · 839 views
2100. Find Good Days to Rob the Bank (Leetcode Medium)Programming Live with Larry · 8:00 · 736 views
Prefix Sum Leetcode 2100 Find Good Days to Rob the BankCoding BeTounsi · 13:02 · 357 views
Find Good Days to Rob the Bank LeetCodeHustler Den · 3:56 · 143 views
LeetCode 2100: Find Good Days to Rob the BankAlitaCode · 31:25 · 15 views
The 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
timedays before and after theithday, - The number of guards at the bank for the
timedays beforeiare non-increasing, and - The number of guards at the bank for the
timedays afteriare 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 <= 105
Approach overview
Problem 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 1: Two-Pass Approach with Auxiliary Arrays
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.
def good_days_to_rob_bank(security, time):
n = len(security)
left = [0] * n
right = [0] * n
# Fill left array
for i in range(1, n):
if security[i] <= security[i - 1]:
left[i] = left[i - 1] + 1
# Fill right array
for i in range(n - 2, -1, -1):
if security[i] <= security[i + 1]:
right[i] = right[i + 1] + 1
# Find good days
result = []
for i in range(time, n - time):
if left[i] >= time and right[i] >= time:
result.append(i)
return result
security = [5,3,3,3,5,6,2]
time = 2
print("Good days:", good_days_to_rob_bank(security, time))import java.util.*;
public class Solution {
public List<Integer> goodDaysToRobBank(int[] security, int time) {
int n = security.length;
int[] left = new int[n];
int[] right = new int[n];
// Fill the left array
for (int i = 1; i < n; i++) {
if (security[i] <= security[i - 1]) {
left[i] = left[i - 1] + 1;
}
}
// Fill the right array
for (int i = n - 2; i >= 0; i--) {
if (security[i] <= security[i + 1]) {
right[i] = right[i + 1] + 1;
}
}
List<Integer> result = new ArrayList<>();
for (int i = time; i < n - time; i++) {
if (left[i] >= time && right[i] >= time) {
result.add(i);
}
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] security = {5,3,3,3,5,6,2};
List<Integer> goodDays = sol.goodDaysToRobBank(security, 2);
System.out.println("Good days: " + goodDays);
}
}#include <vector>
#include <iostream>
using namespace std;
vector<int> goodDaysToRobBank(const vector<int>& security, int time) {
int size = security.size();
vector<int> left(size, 0), right(size, 0);
// Fill left array
for (int i = 1; i < size; ++i) {
if (security[i] <= security[i - 1]) {
left[i] = left[i - 1] + 1;
}
}
// Fill right array
for (int i = size - 2; i >= 0; --i) {
if (security[i] <= security[i + 1]) {
right[i] = right[i + 1] + 1;
}
}
vector<int> result;
for (int i = time; i < size - time; ++i) {
if (left[i] >= time && right[i] >= time) {
result.push_back(i);
}
}
return result;
}
int main() {
vector<int> security = {5,3,3,3,5,6,2};
vector<int> goodDays = goodDaysToRobBank(security, 2);
cout << "Good days: ";
for (int day : goodDays) {
cout << day << " ";
}
cout << endl;
return 0;
}function goodDaysToRobBank(security, time) {
const n = security.length;
const left = new Array(n).fill(0);
const right = new Array(n).fill(0);
for (let i = 1; i < n; i++) {
if (security[i] <= security[i - 1]) {
left[i] = left[i - 1] + 1;
}
}
for (let i = n - 2; i >= 0; i--) {
if (security[i] <= security[i + 1]) {
right[i] = right[i + 1] + 1;
}
}
const result = [];
for (let i = time; i < n - time; i++) {
if (left[i] >= time && right[i] >= time) {
result.push(i);
}
}
return result;
}
const security = [5,3,3,3,5,6,2];
const time = 2;
console.log("Good days:", goodDaysToRobBank(security, time));#include <stdio.h>
#include <stdlib.h>
int* goodDaysToRobBank(int* security, int size, int time, int* returnSize) {
int* left = (int*)calloc(size, sizeof(int));
int* right = (int*)calloc(size, sizeof(int));
// Compute the left non-increasing sequence lengths
for (int i = 1; i < size; i++) {
if (security[i] <= security[i-1]) {
left[i] = left[i-1] + 1;
}
}
// Compute the right non-decreasing sequence lengths
for (int i = size - 2; i >= 0; i--) {
if (security[i] <= security[i+1]) {
right[i] = right[i+1] + 1;
}
}
int* result = (int*)malloc(size * sizeof(int));
*returnSize = 0;
for (int i = time; i < size - time; i++) {
if (left[i] >= time && right[i] >= time) {
result[(*returnSize)++] = i;
}
}
free(left);
free(right);
return result;
}
int main() {
int security[] = {5,3,3,3,5,6,2};
int returnSize;
int* goodDays = goodDaysToRobBank(security, 7, 2, &returnSize);
printf("Good days: ");
for (int i = 0; i < returnSize; i++) {
printf("%d ", goodDays[i]);
}
printf("\n");
free(goodDays);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<int> GoodDaysToRobBank(int[] security, int time) {
int n = security.Length;
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<int> result = new List<int>();
for (int i = time; i < n - time; i++) {
if (left[i] >= time && right[i] >= time) {
result.Add(i);
}
}
return result;
}
public static void Main() {
Solution sol = new Solution();
int[] security = {5,3,3,3,5,6,2};
IList<int> goodDays = sol.GoodDaysToRobBank(security, 2);
Console.WriteLine("Good days: " + string.Join(", ", goodDays));
}
}This Python function calculates the 'good' days by first establishing the proper sequences using two lists to monitor the security levels over time. It iterates to fill these lists, and then it determines the valid days by checking both sequence conditions for each day.
Time Complexity: O(n).
Space Complexity: O(n).
Approach 2: Sliding Window with Prefix 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.
def good_days_to_rob_bank(security, time):
n = len(security)
if time == 0:
return list(range(n))
left_prefix = [0] * n
right_prefix = [0] * n
for i in range(1, n):
left_prefix[i] = left_prefix[i - 1] + (1 if security[i] <= security[i - 1] else 0)
for i in range(n - 2, -1, -1):
right_prefix[i] = right_prefix[i + 1] + (1 if security[i] <= security[i + 1] else 0)
result = []
for i in range(time, n - time):
if left_prefix[i] >= time and right_prefix[i] >= time:
result.append(i)
return result
security = [5,3,3,3,5,6,2]
time = 2
print("Good days:", good_days_to_rob_bank(security, time))function goodDaysToRobBank(security, time) {
const n = security.length;
if (time === 0) return Array.from({length: n}, (_, i) => i);
const leftPrefix = new Array(n).fill(0);
const rightPrefix = new Array(n).fill(0);
for (let i = 1; i < n; i++) {
leftPrefix[i] = (security[i] <= security[i - 1]) ? leftPrefix[i - 1] + 1 : 0;
}
for (let i = n - 2; i >= 0; i--) {
rightPrefix[i] = (security[i] <= security[i + 1]) ? rightPrefix[i + 1] + 1 : 0;
}
const result = [];
for (let i = time; i < n - time; i++) {
if (leftPrefix[i] >= time && rightPrefix[i] >= time) {
result.push(i);
}
}
return result;
}
const security = [5,3,3,3,5,6,2];
const time = 2;
console.log("Good days:", goodDaysToRobBank(security, time));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.
Time Complexity: O(n).
Space Complexity: O(n).
Approach 3: Default Approach
function goodDaysToRobBank(security: number[], time: number): number[] {
const n = security.length;
if (n <= time * 2) {
return [];
}
const l = new Array(n).fill(0);
const r = new Array(n).fill(0);
for (let i = 1; i < n; i++) {
if (security[i] <= security[i - 1]) {
l[i] = l[i - 1] + 1;
}
if (security[n - i - 1] <= security[n - i]) {
r[n - i - 1] = r[n - i] + 1;
}
}
const res = [];
for (let i = time; i < n - time; i++) {
if (time <= Math.min(l[i], r[i])) {
res.push(i);
}
}
return res;
}func goodDaysToRobBank(security []int, time int) []int {
n := len(security)
if n <= time*2 {
return []int{}
}
left := make([]int, n)
right := make([]int, n)
for i := 1; i < n; i++ {
if security[i] <= security[i-1] {
left[i] = left[i-1] + 1
}
}
for i := n - 2; i >= 0; i-- {
if security[i] <= security[i+1] {
right[i] = right[i+1] + 1
}
}
var ans []int
for i := time; i < n-time; i++ {
if time <= left[i] && time <= right[i] {
ans = append(ans, i)
}
}
return ans
}use std::cmp::Ordering;
impl Solution {
pub fn good_days_to_rob_bank(security: Vec<i32>, time: i32) -> Vec<i32> {
let time = time as usize;
let n = security.len();
if time * 2 >= n {
return vec![];
}
let mut g = vec![0; n];
for i in 1..n {
g[i] = match security[i].cmp(&security[i - 1]) {
Ordering::Less => -1,
Ordering::Greater => 1,
Ordering::Equal => 0,
};
}
let (mut a, mut b) = (vec![0; n + 1], vec![0; n + 1]);
for i in 1..=n {
a[i] = a[i - 1] + (if g[i - 1] == 1 { 1 } else { 0 });
b[i] = b[i - 1] + (if g[i - 1] == -1 { 1 } else { 0 });
}
let mut res = vec![];
for i in time..n - time {
if a[i + 1] - a[i + 1 - time] == 0 && b[i + 1 + time] - b[i + 1] == 0 {
res.push(i as i32);
}
}
res
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Two-Pass Approach with Auxiliary Arrays | Time Complexity: O(n). |
| Sliding Window with Prefix Arrays | Time Complexity: O(n). |
| Default Approach | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Find Good Days to Rob the Bank easy or hard?
Find Good Days to Rob the Bank is categorized as a Medium difficulty problem. The logic is straightforward once you recognize the need for preprocessing monotonic streaks, but many candidates initially attempt slower O(n * time) window checks.
Find Good Days to Rob the Bank Python/Java solution
Both Python and Java implementations typically follow the same two-pass logic. First compute non-increasing streaks from the left, then non-decreasing streaks from the right, and finally collect valid indices where both conditions meet the time constraint.
How to solve Find Good Days to Rob the Bank in O(n)?
Precompute two arrays: one storing consecutive non-increasing counts from the left and another storing non-decreasing counts from the right. After these passes, iterate through the array and select indices where both counts are at least time. Each index is processed a constant number of times, giving O(n) complexity.
What is the best approach for Find Good Days to Rob the Bank?
The most common approach uses two passes with auxiliary arrays. Compute how many consecutive non-increasing days occur before each index and how many non-decreasing days occur after it. A day is valid when both counts are at least equal to the given time. This runs in O(n) time with O(n) extra space.
Is Find Good Days to Rob the Bank asked at Google/Amazon/Meta?
Variants of monotonic array scanning and window validation appear in interviews at companies like Amazon and Google. The problem tests array preprocessing, trend tracking, and efficient range validation in linear time.
What data structure is used in Find Good Days to Rob the Bank?
The solution primarily uses arrays to store prefix-like streak counts. These arrays track monotonic trends in the security values so each index can be validated in constant time.
What is the time complexity of Find Good Days to Rob the Bank?
The optimal solution runs in O(n) time where n is the length of the security array. Two linear passes compute monotonic streaks, and a final pass checks valid indices. Space complexity is O(n) for the helper arrays.