Find Good Days to Rob the Bank

Find Good Days to Rob the Bank

What is this problem about?

In the Find Good Days to Rob the Bank coding problem, you are given an array of security values for a bank over $n$ days and an integer time. A day $i$ is considered a "good day" to rob the bank if:

1. The security values for the time days before day $i$ are non-increasing.
2. The security values for the time days after day $i$ are non-decreasing. You need to return a list of all such "good" indices.

Why is this asked in interviews?

Amazon and Google use this problem to test a candidate's ability to avoid redundant calculations. A naive approach would re-check the neighbors for every single day, leading to $O(n imes time)$ complexity. The Dynamic Programming or Prefix Sum interview pattern is required here to solve the problem in linear $O(n)$ time. It tests whether you can precompute data to answer range-based queries instantly.

Algorithmic pattern used

This problem uses Precomputation (Dynamic Programming).

1. Create an array nonIncreasing: left[i] stores how many consecutive days ending at $i$ have been non-increasing.
2. Create an array nonDecreasing: right[i] stores how many consecutive days starting at $i$ are non-decreasing.
3. Iterate through the days and populate left (left-to-right) and right (right-to-left).
4. A day $i$ is "good" if left[i] >= time and right[i] >= time.

Example explanation

security = [5, 3, 3, 3, 5, 6, 2], time = 2

1. Left (non-increasing):
   • Index 0: 0
   • Index 1: 1 (5, 3)
   • Index 2: 2 (5, 3, 3)
   • Index 3: 3 (5, 3, 3, 3)
2. Right (non-decreasing):
   • Index 2: 2 (3, 3, 5)
   • Index 3: 2 (3, 5, 6)
3. Check Day 2: Left[2]=2, Right[2]=2. Good!
4. Check Day 3: Left[3]=3, Right[3]=2. Good! Result: [2, 3].

Common mistakes candidates make

• Nested Loops: Trying to validate every day by scanning its neighbors, which fails for large inputs.
• Wait for exact count: Thinking you need exactly time days, rather than at least time days.
• Boundary errors: Not handling the start and end of the array where time days simply don't exist.

Interview preparation tip

Practice the "Two-Pass Precomputation" pattern. Many array problems that involve conditions on both the left and right sides of an element can be solved by running one pass in each direction and then intersecting the results.