Find Good Days to Rob the Bank

#760 Most AskedMedium

Find Good Days to Rob the Bank #760 Most Asked

Medium

6 views

Topics:

ArraysDynamic Programming

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.

More formally, this means day i is a good day to rob the bank if and only if security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... <= security[i + time - 1] <= security[i + time].

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.

Example 1:

Input: security = [5,3,3,3,5,6,2], time = 2
Output: [2,3]
Explanation:
On day 2, we have security[0] >= security[1] >= security[2] <= security[3] <= security[4].
On day 3, we have security[1] >= 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]
Explanation:
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: []
Explanation:
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 <= 10⁵
0 <= security[i], time <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the `security` array? Could they be negative?
What constitutes a 'good day'? Is 'days' defined as contiguous blocks or can there be gaps?
If there are no good days to rob the bank, what should I return: an empty list or `null`?
What are the constraints on the length of the `security` array and the value of `time`? Specifically, what is the maximum value of `time`?
If multiple valid ranges of days are 'good days', in what order should the returned indices be presented?

Brute Force Solution

Approach

The brute force method to find good days to rob a bank is all about checking every single possible day and seeing if it meets the conditions. We will look at each day one by one, without skipping any.

Here's how the algorithm would work step-by-step:

Start with the first possible day to rob.
Check if the few days leading up to that day show a decreasing trend in security measures.
Also check if the few days following that day show an increasing trend in security measures.
If both the decreasing and increasing trends are true for that particular day, mark it as a good day.
Move on to the next day and repeat the checking process.
Keep doing this until you've checked every single day within the possible range.
Once you've gone through all the days, you'll have a list of all the good days to rob the bank.

Code Implementation

def find_good_days_brute_force(security_measures, time_period):
    good_days = []
    number_of_days = len(security_measures)

    for current_day in range(number_of_days):
        is_good_day = True

        # Check for decreasing trend before current day
        if current_day >= time_period:
            for past_day in range(current_day - time_period, current_day):
                if security_measures[past_day] < security_measures[past_day - 1]:
                    is_good_day = False
                    break

        else:
            is_good_day = False

        #Check for increasing trend after current day
        if is_good_day and current_day + time_period < number_of_days:
            #We only check the future days if the past days check out first.
            for future_day in range(current_day + 1, current_day + time_period + 1):
                if security_measures[future_day] < security_measures[future_day - 1]:
                    is_good_day = False
                    break
        else:
            is_good_day = False

        if is_good_day:
            good_days.append(current_day)

    return good_days

Big(O) Analysis

Time Complexity

O(n*k) – The algorithm iterates through each day of the bank schedule, which has a length of n. For each day, it checks if the k days leading up to it are in decreasing order and if the k days following it are in increasing order. Thus, for each of the n days, we perform two checks, each involving k iterations. Therefore, the total number of operations is proportional to n multiplied by k, resulting in a time complexity of O(n*k).

Space Complexity

O(1) – The brute force approach, as described, iterates through each day and checks for increasing/decreasing trends using only a few constant space variables. It doesn't involve any auxiliary data structures like temporary arrays, lists, or hash maps to store intermediate results or track visited days. The space used is independent of the input size N (where N is the number of days). Therefore, the space complexity remains constant.

Optimal Solution

Approach

We need to find days when the robbery conditions are ideal: a certain number of days before and after must have a decreasing trend beforehand and an increasing trend after. The clever trick is to precompute the lengths of increasing and decreasing sequences at each day to avoid redundant calculations. By doing this precomputation, we can quickly check if a day is 'good' by simply looking up precomputed information.

Here's how the algorithm would work step-by-step:

First, figure out for each day how many days leading up to it have a decreasing trend.
Then, figure out for each day how many days after it have an increasing trend.
Now, check each day to see if it's a 'good' day. To do this, simply check if we have enough decreasing days leading up to it, and enough increasing days after it, based on the required number of days.
If a day meets the above condition, then it's a 'good' day and add it to the list of good days.
Return the list of good days in order.

Code Implementation

def find_good_days_to_rob_the_bank(security, days):
    number_of_days = len(security)
    decreasing_streaks = [0] * number_of_days
    increasing_streaks = [0] * number_of_days

    # Precompute decreasing streaks
    for i in range(1, number_of_days):
        if security[i] <= security[i - 1]:
            decreasing_streaks[i] = decreasing_streaks[i - 1] + 1

    # Precompute increasing streaks
    for i in range(number_of_days - 2, -1, -1):
        if security[i] <= security[i + 1]:
            increasing_streaks[i] = increasing_streaks[i + 1] + 1

    good_days = []

    # Identify good days based on the precomputed streaks
    for i in range(days, number_of_days - days):
        if decreasing_streaks[i] >= days and increasing_streaks[i] >= days:
        # Check if current day has required decreasing and increasing days
            good_days.append(i)

    return good_days

Big(O) Analysis

Time Complexity

O(n) – The algorithm involves iterating through the input array of size n three times. The first iteration calculates the decreasing sequence lengths for each day. The second iteration calculates the increasing sequence lengths for each day. The final iteration checks each day to see if it satisfies the 'good' day condition based on the precomputed lengths. Since each of these iterations is performed in linear time, the overall time complexity is O(n + n + n), which simplifies to O(n).

Space Complexity

O(N) – The solution uses two auxiliary arrays, `left` and `right`, to store the lengths of decreasing and increasing sequences, respectively. Both arrays have the same length as the input `piles` array, which we denote as N. Therefore, the space used by these arrays is proportional to N. No other significant data structures are used, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty security array or invalid input parameters (days <= 0)	Return an empty list if the security array is null or empty, or if days is less than or equal to 0.
Security array size is less than 2 * days + 1	Return an empty list as it's impossible to find a 'good' day with the required neighbors.
Days value is larger than half the array length (integer division), making a valid day impossible	Handle by returning an empty array since 'days' is too large, exceeding the valid window size.
Array contains all identical values	The non-increasing and non-decreasing checks will still function correctly as equality satisfies both conditions.
Array has a monotonically increasing or decreasing security value sequence	The prefix/suffix calculations should handle these patterns correctly, potentially resulting in no good days.
Integer overflow when calculating prefix/suffix arrays with very large security values	The problem statement does not specify the need to avoid integer overflow, assume that the numbers are bounded or use a long data type.
Large array size that leads to memory constraints when creating prefix/suffix arrays	The given solution creates prefix and suffix arrays, so large array sizes could cause memory issues; confirm with the interviewer if in-place modifications are allowed to reduce memory footprint.
No good days exist in the given security array	The algorithm should correctly identify that no indices satisfy the 'good day' condition and return an empty list.

Empty security array or invalid input parameters (days <= 0)

How to Handle:

Return an empty list if the security array is null or empty, or if days is less than or equal to 0.

Security array size is less than 2 * days + 1

How to Handle:

Return an empty list as it's impossible to find a 'good' day with the required neighbors.

Days value is larger than half the array length (integer division), making a valid day impossible

How to Handle:

Handle by returning an empty array since 'days' is too large, exceeding the valid window size.

Array contains all identical values

How to Handle:

The non-increasing and non-decreasing checks will still function correctly as equality satisfies both conditions.

Array has a monotonically increasing or decreasing security value sequence

How to Handle:

The prefix/suffix calculations should handle these patterns correctly, potentially resulting in no good days.

Integer overflow when calculating prefix/suffix arrays with very large security values

How to Handle:

The problem statement does not specify the need to avoid integer overflow, assume that the numbers are bounded or use a long data type.

Large array size that leads to memory constraints when creating prefix/suffix arrays

How to Handle:

The given solution creates prefix and suffix arrays, so large array sizes could cause memory issues; confirm with the interviewer if in-place modifications are allowed to reduce memory footprint.

No good days exist in the given security array

How to Handle:

The algorithm should correctly identify that no indices satisfy the 'good day' condition and return an empty list.