2100. Find Good Days to Rob the Bank


Problem Description

In this problem, you are working with a group of thieves planning a bank heist. You have access to information about the bank's security, specifically the number of guards on duty on each day. The objective is to identify the days on which robbing the bank would be most feasible, based on the security guard patterns.

You are given two inputs:

  1. A list of integers, security, where security[i] represents the number of guards on duty on day i.
  2. An integer, time, which determines the number of days before and after day i that you must consider when evaluating if it’s a good day to commit the robbery.

A day i is considered a good day to rob the bank if the following conditions are met:

  • There's a span of at least time days before and after day i.
  • The number of guards decreases or stays the same on each of the time days before day i.
  • The number of guards increases or stays the same on each of the time days after day i.

Formally, this means day i can be chosen if security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... <= security[i + time - 1] <= security[i + time].

The goal is to return a list of all the days that meet these criteria. It’s important to note that the days in the returned list do not need to be in any particular order.

Intuition

To arrive at the solution for this problem, we need to analyze the pattern of guards before and after each potential day i. Specifically, we want to find days where there's a non-increasing number of guards for time days before i, and a non-decreasing number of guards for time days after i.

Here's the intuition behind the solution:

  • First, we need to handle an edge case. If the total number of days available (n) is not sufficient to have time days before and after any given day, (i.e., if n <= time * 2), it's not possible to find any suitable day for the heist.
  • We use two lists, left and right, to keep track of how many consecutive days before and after day i (including day i itself) satisfy the non-increasing and non-decreasing conditions, respectively.
  • We iterate through the security list to fill out the left list. Starting from the second day (index 1), we check if the number of guards is less than or equal to the number of guards the day before. If it is, we increment the count from the previous day in the left list. This gives us the number of days counting backward from i with non-increasing guards.
  • We do a similar iteration for the right list, but in reverse order, starting at the second-to-last day and moving backwards. If the number of guards is less than or equal to the number of guards the following day, we increment the count from the following day in the right list to get the number of days counting forward from i with non-decreasing guards.
  • Once we have the left and right lists populated, we can iterate through them and select days i where both the left and right values are at least time.
  • These days are our candidates for when the bank can be robbed, and we return these days as our final result.

The solution effectively uses dynamic programming concepts, where we build up our knowledge of guard patterns before and after each day, saving time by not needing to re-calculate the patterns for each day from scratch.

Solution Approach

To implement the solution for finding the best days to rob a bank, the following approach is used:

  1. Initialize Variables: Firstly, we establish the length of the security list and create two lists, left and right, of the same length initialized to zeros. These lists will be used to track the count of consecutive days meeting the conditions leading up to (for left) and following (for right) each index in security.

  2. Populate the left List: We iterate through the security list from the second element to the end (for i in range(1, n)). For each day i, if the number of guards is the same or fewer (security[i] <= security[i - 1]), it means the conditions for a non-increasing sequence up to day i are satisfied. Therefore, we increment the count from the day before in the left list (left[i] = left[i - 1] + 1).

  3. Populate the right List: Similarly, we iterate through the security list in the reverse order starting from the second-to-last element (for i in range(n - 2, -1, -1)). If the number of guards is the same or fewer compared to the next day (security[i] <= security[i + 1]), the non-decreasing condition is satisfied for the time frame after day i. Consequently, we increment the count from the next day in the right list (right[i] = right[i + 1] + 1).

  4. Identify Good Days: After building the left and right lists, the next step is to go through each day and check if it can be considered a good day for the robbery ([i for i in range(n) if time <= min(left[i], right[i])]). A day i is suitable if there's a non-increasing sequence of day counts in left and a non-decreasing sequence in right, both of at least length time. This is checked by confirming the value at index i in both left and right lists are greater than or equal to time. Days that meet these criteria are added to our result list.

  5. Return Result: The final operation returns the list of days that are good for a bank robbery.

This implementation is efficient with a time complexity of O(n), where n is the number of days, because it makes a single pass through the security list for populating left and right lists and then another pass to collect the good days.

The data structures and algorithms used in this solution are characteristic of dynamic programming, where the problem is broken down into simpler subproblems (identifying non-increasing and non-decreasing sequences) that are solved once and used in the final computation.

Example Walkthrough

Let's illustrate the solution approach with a small example. Suppose the input is as follows:

  • security: [3, 4, 3, 2, 4, 1, 5]
  • time: 2

Following the solution approach:

  1. Initialize Variables: We have security with length n = 7. We initialize two lists, left and right, with zeros: left = [0, 0, 0, 0, 0, 0, 0] and right = [0, 0, 0, 0, 0, 0, 0].

  2. Populate the left List: We iterate from the second element:

    • For i = 1, security[i] is 4 and security[i-1] is 3, so left[1] remains 0 (guards increased).
    • For i = 2, security[i] is 3 and security[i-1] is 4, so left[2] becomes left[1] + 1 = 1.
    • For i = 3, security[i] is 2 and security[i-1] is 3, so left[3] becomes left[2] + 1 = 2.
    • Continuing this process, we get left = [0, 0, 1, 2, 0, 1, 0].
  3. Populate the right List: Iterating in reverse order starting from the second-to-last element:

    • For i = 5, security[i] is 1 and security[i+1] is 5, so right[5] becomes right[6] + 1 = 1.
    • For i = 4, security[i] is 4 and security[i+1] is 1, so right[4] remains 0 (guards decreased).
    • For i = 3, security[i] is 2 and security[i+1] is 4, so right[3] becomes right[4] + 1 = 1.
    • Continuing this process, we get right = [0, 0, 0, 1, 0, 1, 0].
  4. Identify Good Days: Now we check each day:

    • Day 2 (index 1) is not good because min(left[1], right[1]) is 0, which is less than time.
    • Day 3 (index 2) is not good because min(left[2], right[2]) is 0, less than time.
    • Day 4 (index 3) is a good day because min(left[3], right[3]) is 1, which equals time.
    • No other day meets the criteria, so we get the result list as [3] (using indices starting from 0).
  5. Return Result: The final returned result is [3], indicating that the only good day for the robbery is day 4, if we consider the days indexed starting from 1.

In this example, only day 4 fulfills the condition of having a non-increasing sequence for time days before it and a non-decreasing sequence for time days after it. Thus, according to our algorithm, this would be the suitable day to plan the heist.

Python Solution

1from typing import List  # Import the List type from the typing module
2
3class Solution:
4    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:
5        # Get the total number of days to analyze
6        num_days = len(security)
7      
8        # If the total number of days is less than twice the required time, return empty list
9        if num_days <= time * 2:
10            return []
11      
12        # Initialize two lists to keep track of the non-increasing and non-decreasing sequences
13        non_increasing = [0] * num_days
14        non_decreasing = [0] * num_days
15      
16        # Count the number of days before the current day where the security value is non-increasing
17        for i in range(1, num_days):
18            if security[i] <= security[i - 1]:
19                non_increasing[i] = non_increasing[i - 1] + 1
20      
21        # Count the number of days after the current day where the security value is non-decreasing
22        for i in range(num_days - 2, -1, -1):
23            if security[i] <= security[i + 1]:
24                non_decreasing[i] = non_decreasing[i + 1] + 1
25      
26        # Find the days where the non-increasing and non-decreasing counts satisfy the time constraint
27        good_days = [i for i in range(num_days) if time <= min(non_increasing[i], non_decreasing[i])]
28      
29        return good_days  # Return the list of good days to rob the bank
30

Java Solution

1class Solution {
2    public List<Integer> goodDaysToRobBank(int[] security, int time) {
3        // Get the length of the `security` array.
4        int n = security.length;
5        // If the length is not sufficient to have days before and after the time period, return an empty list.
6        if (n <= time * 2) {
7            return Collections.emptyList();
8        }
9      
10        // Arrays to keep track of the non-increasing trend to the left and non-decreasing trend to the right.
11        int[] nonIncreasingLeft = new int[n];
12        int[] nonDecreasingRight = new int[n];
13      
14        // Populate the nonIncreasingLeft array by checking if each day is non-increasing compared to the previous day.
15        for (int i = 1; i < n; ++i) {
16            if (security[i] <= security[i - 1]) {
17                nonIncreasingLeft[i] = nonIncreasingLeft[i - 1] + 1;
18            }
19        }
20      
21        // Populate the nonDecreasingRight array by checking if each day is non-decreasing compared to the next day.
22        for (int i = n - 2; i >= 0; --i) {
23            if (security[i] <= security[i + 1]) {
24                nonDecreasingRight[i] = nonDecreasingRight[i + 1] + 1;
25            }
26        }
27      
28        // To store the good days to rob the bank.
29        List<Integer> goodDays = new ArrayList<>();
30      
31        // Check each day to see if it can be a good day to rob the bank.
32        for (int i = time; i < n - time; ++i) {
33            // A day is good if there are at least `time` days before and after it forming non-increasing and non-decreasing trends.
34            if (time <= Math.min(nonIncreasingLeft[i], nonDecreasingRight[i])) {
35                goodDays.add(i);
36            }
37        }
38        // Return the list of good days.
39        return goodDays;
40    }
41}
42

C++ Solution

1#include <vector>
2
3class Solution {
4public:
5    // Function to find the days when it is good to rob the bank.
6    std::vector<int> goodDaysToRobBank(std::vector<int>& security, int time) {
7        // Get the size of the security vector
8        int n = security.size();
9
10        // If the total days are not enough to have 'time' days before and after, return empty list
11        if (n <= time * 2) return {};
12
13        // Dynamic programming arrays to store the non-increasing and non-decreasing streaks
14        std::vector<int> left(n, 0);   // From the left (non-increasing streak lengths)
15        std::vector<int> right(n, 0);  // From the right (non-decreasing streak lengths)
16
17        // Calculate the non-increasing streak from the left
18        for (int i = 1; i < n; ++i) {
19            if (security[i] <= security[i - 1]) {
20                left[i] = left[i - 1] + 1;
21            }
22        }
23
24        // Calculate the non-decreasing streak from the right
25        for (int i = n - 2; i >= 0; --i) {
26            if (security[i] <= security[i + 1]) {
27                right[i] = right[i + 1] + 1;
28            }
29        }
30
31        // Vector to store the good days to rob the bank
32        std::vector<int> ans;
33
34        // Corrected the typo 'tiem' to 'time'
35        for (int i = time; i < n - time; ++i) {
36            // Check if the non-increasing streak on the left and the non-decreasing streak on the right
37            // are both at least 'time' days long
38            if (time <= std::min(left[i], right[i])) {
39                ans.push_back(i); // If the condition is satisfied, it's a good day to rob
40            }
41        }
42      
43        // Return the resultant vector of good days to rob the bank
44        return ans;
45    }
46};
47

Typescript Solution

1function goodDaysToRobBank(security: number[], time: number): number[] {
2    const days = security.length;
3
4    // If there are not enough days to support the 'time' constraint on both sides, return an empty list.
5    if (days <= time * 2) {
6        return [];
7    }
8
9    // Left and right arrays to track the number of non-increasing and non-decreasing days, respectively.
10    const nonIncreasingCounts = new Array(days).fill(0);
11    const nonDecreasingCounts = new Array(days).fill(0);
12
13    // Fill in the nonIncreasingCounts and nonDecreasingCounts arrays.
14    for (let i = 1; i < days; i++) {
15        if (security[i] <= security[i - 1]) {
16            nonIncreasingCounts[i] = nonIncreasingCounts[i - 1] + 1;
17        }
18        if (security[days - i - 1] <= security[days - i]) {
19            nonDecreasingCounts[days - i - 1] = nonDecreasingCounts[days - i] + 1;
20        }
21    }
22
23    // Initialize the response array to store good days to rob the bank.
24    const goodDays = [];
25
26    // Iterate to find good days according to the 'time' constraint.
27    for (let i = time; i < days - time; i++) {
28        // Check if the current day is a good day by comparing non-increasing and non-decreasing counts to 'time'.
29        if (time <= Math.min(nonIncreasingCounts[i], nonDecreasingCounts[i])) {
30            goodDays.push(i);
31        }
32    }
33
34    // Return the list of good days to rob the bank.
35    return goodDays;
36}
37

Time and Space Complexity

Time Complexity

The time complexity of the provided code can be broken down into the following parts:

  1. Initializing the left and right arrays, each with a length of n: This operation takes O(n) time.
  2. Filling in the left array with the lengths of non-increasing subsequences from the left: This requires iterating over the entire security list of length n, resulting in O(n) time.
  3. Filling in the right array with the lengths of non-decreasing subsequences from the right: Similar to the left array, we iterate once in reverse over the length of the security list, which takes O(n) time.
  4. Constructing the list of good days to rob the bank: We again iterate over the security list and compare the left and right values, which is an O(n) operation.

Adding all these operations together, the time complexity is O(n) + O(n) + O(n) + O(n), which simplifies to O(n).

Space Complexity

The space complexity of the code can also be analyzed based on the data structures being used:

  1. The left and right arrays, both of which are of size n: These contribute 2n space complexity.
  2. The result list that is output has at most n elements. However, this space is accounted for in the result and not typically counted towards auxiliary space being used by the algorithm.

Considering these two factors, the space complexity is O(n) for the auxiliary space used, not including the output data structure.


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫