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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Good Days to Rob the Bank

Difficulty: Medium

Problem Description

You and a gang of thieves are planning on robbing a bank. You are given a 0-indexed integer array security, where security[i] is the number of guards on duty on the i-th day. The days are numbered starting from 0. You are also given an integer time. The i-th day is a good day to rob the bank if:

  • There are at least time days before and after the i-th day,
  • The number of guards at the bank for the time days before i are non-increasing, and
  • The number of guards at the bank for the time days after i are non-decreasing.

Return a list of all days (0-indexed) that are good days to rob the bank. The order that the days are returned in does not matter.

Key Insights

  • A day is classified as "good" based on the guards' presence over a specific range of days before and after it.
  • Non-increasing and non-decreasing sequences must be checked for the defined range.
  • The problem can be efficiently solved using two auxiliary arrays to track the lengths of non-increasing and non-decreasing sequences.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve the problem, we can use two arrays: left and right.

  • The left array will store the count of consecutive non-increasing guards up to each day.
  • The right array will store the count of consecutive non-decreasing guards from each day onward.
  1. We will iterate from the beginning of the security array to fill the left array.
  2. We will iterate from the end of the security array to fill the right array.
  3. Finally, we check each day to see if it satisfies the conditions for being a "good" day using the values from the left and right arrays.

Code Solutions

def goodDaysToRobBank(security, time):
    n = len(security)
    if time == 0:
        return list(range(n))

    left = [0] * n
    right = [0] * n

    # Fill the left array
    for i in range(1, n):
        if security[i] <= security[i - 1]:
            left[i] = left[i - 1] + 1

    # Fill the right array
    for i in range(n - 2, -1, -1):
        if security[i] <= security[i + 1]:
            right[i] = right[i + 1] + 1

    # Find all good days
    good_days = []
    for i in range(time, n - time):
        if left[i] >= time and right[i] >= time:
            good_days.append(i)

    return good_days
← Back to All Questions