We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Good Days to Rob the Bank

Number: 2205

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

Given an array of integers representing the number of guards on duty each day, find all the days (0-indexed) that are good for robbing the bank. A day is considered good if there are at least “time” days before and after it, such that the previous “time” days are in non-increasing order and the following “time” days are in non-decreasing order.

Key Insights

  • If time is 0, every day is a good day.
  • Use two passes (one forward and one backward) to precompute how many consecutive days (including the current day) fulfill the non-increasing and non-decreasing conditions.
  • For the left side, count consecutive days where the guard number does not increase.
  • For the right side, count consecutive days where the guard number does not decrease.
  • A valid day must have at least “time” consecutive days on both sides.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the security array. Space Complexity: O(n), for the two auxiliary arrays used during the passes.

Solution

We will use a dynamic programming approach by computing two arrays:

  1. left[]: For each day, it stores the number of consecutive previous days (up to the current day) that form a non-increasing sequence.
  2. right[]: For each day, it stores the number of consecutive following days (starting at the current day) that form a non-decreasing sequence.

For each day i (excluding the first and last “time” days), check if left[i] >= time and right[i] >= time. If so, add i to the result list.

The key trick here is to count the sequences in one pass to avoid rechecking each window, which keeps the solution efficient.

Code Solutions

# Python Solution

def goodDaysToRobBank(security, time):
    n = len(security)
    # If time is 0, every day is a good day.
    if time == 0:
        return list(range(n))
    
    left = [0] * n  # counts non-increasing days ending at i
    right = [0] * n  # counts non-decreasing days starting at i

    # Build the left array.
    for i in range(1, n):
        # If current day is less or equal to previous day,
        # then extend the non-increasing sequence.
        if security[i] <= security[i - 1]:
            left[i] = left[i - 1] + 1
        else:
            left[i] = 0

    # Build the right array.
    for i in range(n - 2, -1, -1):
        # If current day is less or equal to next day,
        # then extend the non-decreasing sequence.
        if security[i] <= security[i + 1]:
            right[i] = right[i + 1] + 1
        else:
            right[i] = 0

    result = []
    # Check valid days where both left and right sequences have at least 'time' days.
    for i in range(time, n - time):
        if left[i] >= time and right[i] >= time:
            result.append(i)
    
    return result

# Example usage:
# security = [5,3,3,3,5,6,2]
# time = 2
# print(goodDaysToRobBank(security, time))  # Output: [2, 3]
← Back to All Questions