#2100

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Find Good Days to Rob the Bank

Find good days to rob the bank by identifying days with non-increasing and non-decreasing guard counts using dynamic programming.

array dynamic programming prefix sum

Problem Statement

You are part of a gang of thieves planning to rob a bank. You are given a 0-indexed integer array security, where security[i] represents the number of guards on duty on the ith day. The days are numbered starting from 0, and you're also given an integer time.

A day i is a good day to rob the bank if the number of guards in the previous time days is non-increasing and the number of guards in the following time days is non-decreasing. Formally, day i is a good day if the sequence before and after it follows these conditions.

Examples

Example 1

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

Output: [2,3]

On day 2, we have security[0] >= security[1] >= security[2] = 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]

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: []

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

Solution Approach

Brute Force Solution

The simplest solution is to iterate over each day and check if the surrounding days meet the non-increasing and non-decreasing conditions within the time window. This solution is straightforward but inefficient due to redundant comparisons.

Optimized Approach with Dynamic Programming

Instead of recalculating conditions for each day, use dynamic programming to track the prefix sums and transitions, storing results for past computations. This reduces the complexity by reusing the results of previous checks and avoids redundant operations.

Prefix Sum for Guard Transitions

We can further optimize by creating two prefix arrays, one tracking the longest non-increasing sequence and another tracking the longest non-decreasing sequence. By using these precomputed results, we can efficiently check for valid days without needing to re-evaluate all conditions from scratch.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity can be reduced from O(n * time) in the brute force approach to O(n) with dynamic programming, where n is the length of the security array. The space complexity depends on the approach but can be kept to O(n) using prefix sums or dynamic programming arrays.

What Interviewers Usually Probe

Look for an understanding of dynamic programming and how to optimize brute force solutions.
Check if the candidate can think of ways to minimize redundant operations.
Evaluate how well the candidate understands prefix sums and state transitions for optimization.

Common Pitfalls or Variants

Common pitfalls

Failing to recognize the overlap between different days, leading to redundant operations.
Not optimizing the solution beyond brute force, resulting in excessive time complexity.
Missing the use of dynamic programming or prefix sums to reduce the number of checks required.

Follow-up variants

What if time equals 0? In this case, every day is a good day, and the solution needs to handle that scenario.
How would the approach change if the array is reversed? The same principles apply, but adjustments in the direction of the transitions are needed.
If there were additional constraints on the number of guards or days, the solution might need further optimization or adjustments in the approach.

FAQ

What is the primary pattern used to solve the 'Find Good Days to Rob the Bank' problem?

The primary pattern used in this problem is state transition dynamic programming, which optimizes redundant checks using prefix sums.

How can dynamic programming be applied to solve this problem?

Dynamic programming can track the transitions of guard counts before and after each day, optimizing the solution by storing intermediate results and avoiding redundant calculations.

What is the time complexity of the optimal solution for this problem?

The optimal solution has a time complexity of O(n), where n is the length of the security array, using dynamic programming and prefix sums.

Why is the brute force solution inefficient for this problem?

The brute force solution checks each day and evaluates all surrounding days for non-increasing and non-decreasing conditions, leading to O(n * time) time complexity, which is inefficient for large arrays.

What happens if `time` equals 0 in the 'Find Good Days to Rob the Bank' problem?

If time equals 0, every day is a good day to rob the bank, as there are no surrounding days to compare.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:
        n = len(security)
        if n <= time * 2:
            return []
        left, right = [0] * n, [0] * n
        for i in range(1, n):
            if security[i] <= security[i - 1]:
                left[i] = left[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if security[i] <= security[i + 1]:
                right[i] = right[i + 1] + 1
        return [i for i in range(n) if time <= min(left[i], right[i])]

Continue Practicing

#2218 maximum value of k coins from piles #1872 stone game viii #2420 find all good indices