Problem Description

You're given an array security where security[i] represents the number of guards on duty on day i. You need to find all the "good days" to rob a bank based on specific conditions.

A day i is considered a good day to rob the bank if:

1. Sufficient buffer days: There must be at least time days before and after day i. This means i >= time and i + time < n (where n is the length of the array).

2. Non-increasing pattern before: The number of guards for time days leading up to day i should be non-increasing. In other words: security[i - time] >= security[i - time + 1] >= ... >= security[i - 1] >= security[i].

3. Non-decreasing pattern after: The number of guards for time days following day i should be non-decreasing. In other words: security[i] <= security[i + 1] <= ... <= security[i + time - 1] <= security[i + time].

The solution uses a preprocessing approach with two arrays:

• left[i]: Tracks the length of the non-increasing sequence ending at position i
• right[i]: Tracks the length of the non-decreasing sequence starting at position i

For each position i, if both left[i] >= time and right[i] >= time, then day i satisfies all conditions and is a good day to rob the bank.

The function returns a list of all such good days (0-indexed). The order of days in the result doesn't matter.

Example: If security = [5,3,3,3,5,6,2] and time = 2, day 2 and day 3 would be good days because:

• Day 2: The pattern [5,3,3] before (non-increasing) and [3,3,5] after (non-decreasing)
• Day 3: The pattern [3,3,3] before (non-increasing) and [3,5,6] after (non-decreasing)

Intuition

The naive approach would be to check each day i by examining time days before and after it, verifying if the guards follow the required pattern. However, this would result in O(n * time) complexity, which can be inefficient.

The key insight is recognizing that we're looking for days that sit at the "valley" of a specific pattern - where the number of guards decreases (or stays same) leading up to that day, then increases (or stays same) after that day.

Instead of repeatedly checking the same sequences for different days, we can precompute information about monotonic sequences. Consider this: if we know that days 0-4 form a non-increasing sequence, then day 4 can look back 4 days of non-increasing pattern. Similarly, if days 4-7 form a non-decreasing sequence, then day 4 can look forward 3 days of non-decreasing pattern.

This leads us to the preprocessing approach:

• For each position, we calculate how many consecutive days before it form a non-increasing sequence (left array)
• For each position, we calculate how many consecutive days after it form a non-decreasing sequence (right array)

Building left[i]: If security[i] <= security[i-1], then the non-increasing sequence extends, so left[i] = left[i-1] + 1. Otherwise, the sequence breaks and left[i] = 0.

Building right[i]: We traverse backwards. If security[i] <= security[i+1], then this position starts a non-decreasing sequence that extends to the right, so right[i] = right[i+1] + 1.

Once we have these arrays, checking if day i is good becomes simple: we just need left[i] >= time and right[i] >= time. This ensures there are enough non-increasing days before and enough non-decreasing days after day i.

This optimization reduces our time complexity to O(n) with O(n) extra space - a significant improvement over the naive approach.

Learn more about Dynamic Programming and Prefix Sum patterns.

Solution Approach

The implementation follows a three-phase approach: preprocessing left trends, preprocessing right trends, and finding valid days.

Phase 1: Build the left array

We create a left array where left[i] represents the number of consecutive non-increasing days ending at position i.

left = [0] * n
for i in range(1, n):
    if security[i] <= security[i - 1]:
        left[i] = left[i - 1] + 1

Starting from index 1, we check if the current day has guards less than or equal to the previous day. If yes, we extend the non-increasing sequence count by adding 1 to the previous count. Otherwise, left[i] remains 0 (sequence breaks).

Phase 2: Build the right array

We create a right array where right[i] represents the number of consecutive non-decreasing days starting at position i.

right = [0] * n
for i in range(n - 2, -1, -1):
    if security[i] <= security[i + 1]:
        right[i] = right[i + 1] + 1

We traverse backwards from index n-2 to 0. If the current day has guards less than or equal to the next day, we extend the non-decreasing sequence count. This backward traversal is crucial because we're counting days that come after position i.

Phase 3: Find good days

return [i for i in range(n) if time <= min(left[i], right[i])]

For each day i, we check if both left[i] >= time and right[i] >= time. This can be simplified to checking if time <= min(left[i], right[i]). If this condition holds, day i has at least time non-increasing days before it and at least time non-decreasing days after it, making it a good day to rob the bank.

Edge Case Handling

The initial check if n <= time * 2: return [] handles the case where the array is too small to have any valid days. If we need time days before and time days after any day i, the minimum array length must be 2 * time + 1.

Time and Space Complexity

• Time: O(n) - We make three linear passes through the array
• Space: O(n) - We use two auxiliary arrays of size n

Example Walkthrough

Let's walk through a concrete example with security = [5,3,3,3,5,6,2] and time = 2.

Step 1: Build the left array (non-increasing sequences ending at each position)

Starting with left = [0, 0, 0, 0, 0, 0, 0]:

• Index 0: Base case, left[0] = 0
• Index 1: security[1]=3 <= security[0]=5? Yes → left[1] = left[0] + 1 = 1
• Index 2: security[2]=3 <= security[1]=3? Yes → left[2] = left[1] + 1 = 2
• Index 3: security[3]=3 <= security[2]=3? Yes → left[3] = left[2] + 1 = 3
• Index 4: security[4]=5 <= security[3]=3? No → left[4] = 0
• Index 5: security[5]=6 <= security[4]=5? No → left[5] = 0
• Index 6: security[6]=2 <= security[5]=6? Yes → left[6] = left[5] + 1 = 1

Result: left = [0, 1, 2, 3, 0, 0, 1]

Step 2: Build the right array (non-decreasing sequences starting at each position)

Starting with right = [0, 0, 0, 0, 0, 0, 0]:

• Index 6: Base case, right[6] = 0
• Index 5: security[5]=6 <= security[6]=2? No → right[5] = 0
• Index 4: security[4]=5 <= security[5]=6? Yes → right[4] = right[5] + 1 = 1
• Index 3: security[3]=3 <= security[4]=5? Yes → right[3] = right[4] + 1 = 2
• Index 2: security[2]=3 <= security[3]=3? Yes → right[2] = right[3] + 1 = 3
• Index 1: security[1]=3 <= security[2]=3? Yes → right[1] = right[2] + 1 = 4
• Index 0: security[0]=5 <= security[1]=3? No → right[0] = 0

Result: right = [0, 4, 3, 2, 1, 0, 0]

Step 3: Find good days where min(left[i], right[i]) >= time = 2

Check each index:

• Index 0: min(0, 0) = 0 < 2 ❌
• Index 1: min(1, 4) = 1 < 2 ❌
• Index 2: min(2, 3) = 2 >= 2 ✓
• Index 3: min(3, 2) = 2 >= 2 ✓
• Index 4: min(0, 1) = 0 < 2 ❌
• Index 5: min(0, 0) = 0 < 2 ❌
• Index 6: min(1, 0) = 0 < 2 ❌

Result: Days 2 and 3 are good days to rob the bank

Verification:

• Day 2: Has 2 non-increasing days before (5→3→3) and 2 non-decreasing days after (3→5→6)
• Day 3: Has 2 non-increasing days before (3→3→3) and 2 non-decreasing days after (3→5→6)

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the length of the security array.

• The algorithm makes three linear passes through the array:
  1. First loop from index 1 to n-1 to populate the left array: O(n)
  2. Second loop from index n-2 to 0 to populate the right array: O(n)
  3. List comprehension to build the result by checking each index: O(n)
• Each operation within the loops takes constant time O(1)
• Total time complexity: O(n) + O(n) + O(n) = O(n)

Space Complexity: O(n), where n is the length of the security array.

• Two auxiliary arrays left and right are created, each of size n: O(n) + O(n) = O(2n) = O(n)
• The output list in the worst case (when all days are good days to rob) can contain up to n elements: O(n)
• Total space complexity: O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Sequence Counting

The Pitfall: A common mistake is misunderstanding what left[i] and right[i] represent. Developers often incorrectly assume:

• left[i] counts the total non-increasing sequence including position i
• right[i] counts the total non-decreasing sequence including position i

This leads to incorrect implementations like:

# WRONG: This counts the current position in the sequence
for i in range(1, n):
    if security[i] <= security[i - 1]:
        left[i] = left[i - 1] + 1
    else:
        left[i] = 1  # Wrong! Should be 0

Why It's Wrong: The problem requires exactly time days BEFORE and AFTER day i, not including day i itself. The arrays should count:

• left[i]: How many consecutive days before i form a non-increasing sequence
• right[i]: How many consecutive days after i form a non-decreasing sequence

The Solution: Initialize both arrays with 0 and only increment when extending a valid sequence:

left = [0] * n  # Correctly initialized to 0
right = [0] * n

for i in range(1, n):
    if security[i] <= security[i - 1]:
        left[i] = left[i - 1] + 1
    # No else clause needed; left[i] stays 0 if sequence breaks

2. Incorrect Boundary Check

The Pitfall: Using the wrong formula for checking if there's enough space:

# WRONG: This allows arrays that are too small
if n < time * 2:  # Missing the day i itself
    return []

Why It's Wrong: We need:

• time days before day i
• Day i itself
• time days after day i Total minimum length = time + 1 + time = 2 * time + 1

The Solution: Use the correct boundary check:

if n <= time * 2:  # Correct: n must be at least 2*time + 1
    return []

3. Confusing Non-Increasing vs. Strictly Decreasing

The Pitfall: Using strict inequality when the problem requires non-increasing (allowing equal values):

# WRONG: Using strict inequality
if security[i] < security[i - 1]:  # Should be <=
    left[i] = left[i - 1] + 1

Why It's Wrong: The problem specifically states "non-increasing" which means values can be equal. The sequence [5, 3, 3, 3] is valid non-increasing, but using < would break at the equal values.

The Solution: Always use <= for both left and right array construction:

# Correct: non-increasing allows equal values
if security[i] <= security[i - 1]:
    left[i] = left[i - 1] + 1

# Correct: non-decreasing allows equal values  
if security[i] <= security[i + 1]:
    right[i] = right[i + 1] + 1

4. Wrong Direction for Right Array Traversal

The Pitfall: Building the right array from left to right:

# WRONG: Cannot determine future trend going forward
for i in range(n - 1):
    if security[i] <= security[i + 1]:
        right[i] = right[i - 1] + 1  # Wrong logic

Why It's Wrong: To know how many non-decreasing days follow position i, we must traverse backwards. Going forward, we can't know what comes next.

The Solution: Always traverse backwards for the right array:

# Correct: Build right array from right to left
for i in range(n - 2, -1, -1):
    if security[i] <= security[i + 1]:
        right[i] = right[i + 1] + 1