{x}
blog image

Find Good Days to Rob the Bank

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 ith day. The days are numbered starting from 0. You are also given an integer time.

The ith day is a good day to rob the bank if:

  • There are at least time days before and after the ith 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 <= 105
  • 0 <= security[i], time <= 105

Solution Explanation

This problem asks to find "good days" to rob a bank, where a good day satisfies three conditions:

  1. Sufficient Time Window: There must be at least time days before and after the day in question.
  2. Non-increasing Guards Before: The number of guards on duty for time days before the day must be non-increasing.
  3. Non-decreasing Guards After: The number of guards on duty for time days after the day must be non-decreasing.

The most efficient approach is to use two arrays, left and right, to pre-compute the lengths of non-increasing and non-decreasing sequences, respectively. Then, iterate through the security array and check if a day meets the conditions using the pre-computed values.

Algorithm

  1. Initialization: Create two arrays, left and right, of the same size as security. Initialize all elements to 0.

  2. Left Pass: Iterate through security from left to right. If security[i] <= security[i-1], it means the sequence is still non-increasing, so increment left[i] by 1 and add the value from the previous left entry left[i] = left[i-1] + 1. Otherwise, left[i] remains 0. This gives us the length of the longest non-increasing sequence ending at each index.

  3. Right Pass: Iterate through security from right to left. If security[i] <= security[i+1], increment right[i] similar to the left pass. This gives us the length of the longest non-decreasing sequence starting at each index.

  4. Filtering Good Days: Iterate through security from index time to n - time -1 (to ensure there are enough days before and after). If both left[i] and right[i] are greater than or equal to time, then the day i is a "good day" because both preceding and following sequences satisfy the non-increasing/non-decreasing conditions. Add index i to the result list.

  5. Return Result: Return the list of good days.

Time and Space Complexity Analysis

  • Time Complexity: O(N), where N is the length of the security array. This is because we perform three linear scans of the array (left pass, right pass, and filtering).

  • Space Complexity: O(N), due to the use of left and right arrays. The space used by the result list is at most O(N) in the worst-case scenario but is typically less.

Code Implementations (Python, Java, C++, Go, TypeScript, Rust)

The code implementations provided in the original response are efficient and correctly implement the described algorithm. They all achieve the optimal time and space complexity. The variation among the languages lies primarily in syntax and standard library usage. Each example correctly handles edge cases (empty arrays, insufficient time, etc.).