LeetCode 2100 - Find Good Days to Rob the Bank

The problem asks us to find all days that are "good" for robbing a bank based on the number of guards on duty over a period of days.

leetcodemediumarraydynamic-programmingprefix-sum

LeetCode Problem 2100

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Prefix Sum

Solution

Problem Understanding

The problem asks us to find all days that are "good" for robbing a bank based on the number of guards on duty over a period of days. You are given an array security where each element represents the number of guards on a specific day, and an integer time that defines a window before and after a day. A day is considered good if, for time days before it, the number of guards is non-increasing, and for time days after it, the number of guards is non-decreasing.

In other words, for day i to be good, the security levels should form a "valley" pattern around it: the previous time days do not increase, and the next time days do not decrease. The output is a list of all days that satisfy this condition.

Constraints tell us the input array can be up to 100,000 elements, and time can also be large, so brute-force comparisons for every possible day will be too slow. Edge cases include time = 0, which means every day is trivially good, or arrays that are entirely increasing or decreasing, which may produce no valid days. The problem guarantees non-negative integers in the array.

Approaches

The brute-force approach is straightforward. For each day i that has at least time days before and after, we check two separate sequences: the time days before i must be non-increasing, and the time days after i must be non-decreasing. This requires examining 2 * time elements per candidate day. While correct, this results in O(n * time) time complexity, which is too slow for large n and time (up to 10^5).

The optimal approach observes that we do not need to check each subarray repeatedly. We can precompute, for each day, the length of consecutive non-increasing days ending at that day, and the length of consecutive non-decreasing days starting at that day. These arrays, often called non_inc and non_dec, allow us to determine if day i is good in constant time by comparing the lengths to time. This reduces the time complexity to O(n) while using O(n) extra space.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * time) O(1) Check each day with explicit loops for the before and after windows
Optimal O(n) O(n) Use prefix arrays for non-increasing and non-decreasing counts

Algorithm Walkthrough

  1. Initialize two arrays, non_inc and non_dec, both of length n. non_inc[i] will store the number of consecutive days ending at i where the sequence is non-increasing, and non_dec[i] will store the number of consecutive days starting at i where the sequence is non-decreasing.
  2. Fill non_inc by iterating from left to right. For each day i starting from 1, if security[i] <= security[i-1], increment non_inc[i] = non_inc[i-1] + 1. Otherwise, reset it to 0.
  3. Fill non_dec by iterating from right to left. For each day i from n-2 to 0, if security[i] <= security[i+1], increment non_dec[i] = non_dec[i+1] + 1. Otherwise, reset it to 0.
  4. Iterate through all days i from time to n - time - 1. If non_inc[i] >= time and non_dec[i] >= time, append i to the result list.
  5. Return the result list.

Why it works: non_inc[i] measures how many previous days including i are non-increasing, and non_dec[i] measures how many subsequent days including i are non-decreasing. Comparing these to time ensures the "valley" condition is satisfied for each candidate day.

Python Solution

from typing import List

class Solution:
    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:
        n = len(security)
        if time == 0:
            return list(range(n))
        
        non_inc = [0] * n
        non_dec = [0] * n
        
        for i in range(1, n):
            if security[i] <= security[i - 1]:
                non_inc[i] = non_inc[i - 1] + 1
        
        for i in range(n - 2, -1, -1):
            if security[i] <= security[i + 1]:
                non_dec[i] = non_dec[i + 1] + 1
        
        result = []
        for i in range(time, n - time):
            if non_inc[i] >= time and non_dec[i] >= time:
                result.append(i)
        
        return result

The code first handles the edge case where time = 0, returning all days. Then it constructs two arrays for non-increasing and non-decreasing streaks. Finally, it checks each day in the valid range to see if it satisfies the conditions, and returns all good days.

Go Solution

func goodDaysToRobBank(security []int, time int) []int {
    n := len(security)
    if time == 0 {
        result := make([]int, n)
        for i := 0; i < n; i++ {
            result[i] = i
        }
        return result
    }
    
    nonInc := make([]int, n)
    nonDec := make([]int, n)
    
    for i := 1; i < n; i++ {
        if security[i] <= security[i-1] {
            nonInc[i] = nonInc[i-1] + 1
        }
    }
    
    for i := n - 2; i >= 0; i-- {
        if security[i] <= security[i+1] {
            nonDec[i] = nonDec[i+1] + 1
        }
    }
    
    result := []int{}
    for i := time; i < n - time; i++ {
        if nonInc[i] >= time && nonDec[i] >= time {
            result = append(result, i)
        }
    }
    
    return result
}

Go differences: We explicitly create slices of the correct length and handle appending to the result with append. The logic for filling nonInc and nonDec mirrors the Python solution.

Worked Examples

Example 1: security = [5,3,3,3,5,6,2], time = 2

Calculate non_inc:

i:      0 1 2 3 4 5 6
security:5 3 3 3 5 6 2
non_inc:0 1 2 3 0 0 1

Calculate non_dec:

i:      0 1 2 3 4 5 6
security:5 3 3 3 5 6 2
non_dec:0 2 2 1 1 1 0

Check days from time to n-time-1 (2 to 4):

  • i=2: non_inc[2]=2 >= 2 and non_dec[2]=2 >= 2 → good
  • i=3: non_inc[3]=3 >= 2 and non_dec[3]=1 < 2 → good only if counting correctly, actually non_dec[3]=2 → good
  • i=4: non_inc[4]=0 < 2 → not good

Result: [2,3].

Example 2: security = [1,1,1,1,1], time = 0

Return [0,1,2,3,4].

Example 3: security = [1,2,3,4,5,6], time = 2

non_inc never reaches 2 → return [].

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate over the array three times: once to fill non_inc, once for non_dec, and once to collect results.
Space O(n) We store two additional arrays of length n for non-increasing and non-decreasing counts.

The reasoning is that each loop is linear in n, and no nested loops are required, so the solution is efficient even for the largest inputs.

Test Cases

# Provided examples
assert Solution().goodDaysToRobBank([5,3,3,3,5,6,2], 2) == [2,3]  # valley in middle
assert Solution().goodDaysToRobBank([1,1,1,1,1], 0) == [0,1,2,3,4]  # time=0
assert Solution().goodDaysToRobBank([1,2,3,4,5,6], 2) == []  # no good day

# Edge and stress cases
assert Solution().goodDaysToRobBank([1], 0) == [0]  # single day