Find Good Days to Rob the Bank

MEDIUM

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.

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⁵

Approaches

Checkout 2 different approaches to solve Find Good Days to Rob the Bank. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

This approach directly translates the problem statement into code. We iterate through each day that could potentially be a good day to rob the bank. A day i is a potential candidate only if there are at least time days before it and time days after it. This means we only need to check days i in the range [time, n - 1 - time], where n is the total number of days.

Algorithm

Initialize an empty list goodDays to store the result.
Let n be the length of the security array.
Iterate through each day i from time to n - 1 - time. These are the only days that can have time days before and after them.
For each candidate day i, assume it's a good day and check the two conditions:
- Before i: Check if security[j] >= security[j+1] for all j from i - time up to i - 1. If this condition is ever violated, day i is not good, and we can move to the next day i+1.
- After i: If the first condition holds, check if security[j] <= security[j+1] for all j from i up to i + time - 1. If this condition is violated, day i is not good.
If both conditions are met for day i, add i to the goodDays list.
After checking all possible days, return the goodDays list.

For each candidate day i, we perform two separate checks:

Non-increasing before: We check if the number of guards is non-increasing for time days leading up to and including day i. This involves a loop from i - time to i - 1, verifying that security[j] >= security[j+1] for each j.
Non-decreasing after: We check if the number of guards is non-decreasing for time days starting from day i. This involves another loop from i to i + time - 1, verifying that security[j] <= security[j+1] for each j. If both conditions are satisfied, we add the day i to our list of good days.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> goodDaysToRobBank(int[] security, int time) {
        List<Integer> goodDays = new ArrayList<>();
        int n = security.length;

        // Iterate through all possible good days
        for (int i = time; i < n - time; i++) {
            boolean nonIncreasingBefore = true;
            // Check for non-increasing sequence of 'time' days before day i
            for (int j = 1; j <= time; j++) {
                if (security[i - j] < security[i - j + 1]) {
                    nonIncreasingBefore = false;
                    break;
                }
            }

            if (nonIncreasingBefore) {
                boolean nonDecreasingAfter = true;
                // Check for non-decreasing sequence of 'time' days after day i
                for (int j = 1; j <= time; j++) {
                    if (security[i + j - 1] > security[i + j]) {
                        nonDecreasingAfter = false;
                        break;
                    }
                }
                if (nonDecreasingAfter) {
                    goodDays.add(i);
                }
            }
        }
        return goodDays;
    }
}

Complexity Analysis

Time Complexity: O(n * time). The outer loop runs for `n - 2 * time` iterations. Inside it, there are two loops, each running up to `time` times. This results in a total time complexity of `O((n - 2*time) * 2*time)`, which simplifies to `O(n * time)`.Space Complexity: O(1) extra space. The space used for the output list can be up to O(n) in the worst case, but this is often excluded from space complexity analysis.

Pros and Cons

Pros:

Simple to understand and implement as it directly follows the problem's definition.
Low space complexity if the output list is not considered.

Cons:

Highly inefficient for large inputs, especially when time is large. The O(n * time) complexity can lead to a 'Time Limit Exceeded' error on competitive programming platforms.
It performs a lot of redundant computations. For example, when checking day i and day i+1, the check for the overlapping window of days is performed twice.

Code Solutions

Checking out 3 solutions in different languages for Find Good Days to Rob the Bank. Click on different languages to view the code.

class Solution {
public
  List<Integer> goodDaysToRobBank(int[] security, int time) {
    int n = security.length;
    if (n <= time * 2) {
      return Collections.emptyList();
    }
    int[] left = new int[n];
    int[] right = new int[n];
    for (int i = 1; i < n; ++i) {
      if (security[i] <= security[i - 1]) {
        left[i] = left[i - 1] + 1;
      }
    }
    for (int i = n - 2; i >= 0; --i) {
      if (security[i] <= security[i + 1]) {
        right[i] = right[i + 1] + 1;
      }
    }
    List<Integer> ans = new ArrayList<>();
    for (int i = time; i < n - time; ++i) {
      if (time <= Math.min(left[i], right[i])) {
        ans.add(i);
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Find Good Days to Rob the Bank

Patterns:

Dynamic ProgrammingPrefix Sum

Data Structures:

Array