2100. Find Good Days to Rob the Bank
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 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 theith
day, - The number of guards at the bank for the
time
days beforei
are non-increasing, and - The number of guards at the bank for the
time
days afteri
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 doesnot 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
Solutions
Solution: Prefix Sum
- Time complexity: O(n)
- Space complexity: O(n)
JavaScript
js
/**
* @param {number[]} security
* @param {number} time
* @return {number[]}
*/
const goodDaysToRobBank = function (security, time) {
const size = security.length;
const beforeTimes = new Array(size).fill(0);
const afterTimes = new Array(size).fill(0);
const result = [];
for (let index = 1; index < size; index++) {
if (security[index - 1] < security[index]) continue;
beforeTimes[index] = beforeTimes[index - 1] + 1;
}
for (let index = size - 2; index >= 0; index--) {
if (security[index + 1] < security[index]) continue;
afterTimes[index] = afterTimes[index + 1] + 1;
}
for (let index = time; index < size - time; index++) {
if (beforeTimes[index] < time || afterTimes[index] < time) continue;
result.push(index);
}
return result;
};