Skip to main content
Talentd

Find Good Days to Rob the Bank - Solution & Explanation

MediumArrayDynamic ProgrammingPrefix Sum13 min readAsked at: Amazon, Google
Practice this problem

Problem Statement

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 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 <= 105
  • 0 <= 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.

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

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.

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n).
Space Complexity: O(n).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.
Space Complexity: O(n) — for storing the 'left' and 'right' auxiliary arrays.

Sliding Window with Prefix Arrays

Time Complexity: O(n).
Space Complexity: O(n).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pass with Auxiliary ArraysO(n)O(n)Standard interview solution; easy to implement and reason about monotonic streaks
Sliding Window with Prefix ArraysO(n)O(n)Useful when validating window constraints using prefix counts instead of streak arrays

Video Solution

Find Good Days to Rob the Bank | Leetcode 2100 | Live coding session 🔥🔥🔥 | Linear approach • Coding Decoded • 2,677 views views

Watch 5 more video solutions →

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.

Ready to solve this problem?

Practice Find Good Days to Rob the Bank with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find All Good Indices

Next

Find in Mountain Array