2100

2100. Find Good Days to Rob the Bank (Medium)

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.

Example 4:

Input: security = [1], time = 5
Output: []
Explanation:
No day has 5 days before and after it.
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

Similar Questions:

• Non-decreasing Array (Medium)
• Longest Mountain in Array (Medium)
• Find in Mountain Array (Hard)
• Maximum Ascending Subarray Sum (Easy)

Solution 1. Monotonic Deque

For a window [i - time, i + time], use two monotonic deques a and b to track the numbers in the first half [i - time, i] and second half [i, i + time] of the window.

Keep a monotonic non-increasing and b monotonic non-decreasing.

If both a.size() and b.size() equal time + 1, we add the current index i into the answer.

// OJ: https://leetcode.com/problems/find-good-days-to-rob-the-bank/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(T)
class Solution {
public:
    vector<int> goodDaysToRobBank(vector<int>& A, int time) {
        deque<int> a, b;
        vector<int> ans;
        for (int i = 0; i + time < A.size(); ++i) {
            while (a.size() && A[a.back()] < A[i]) a.pop_back(); // Before pushing `i`, pop the indexes at the back of the deque whose corresponding value `< A[i]`
            a.push_back(i);
            if (a.front() < i - time) a.pop_front(); // Pop index if it's out of window
            while (b.size() && A[b.back()] > A[i + time]) b.pop_back(); // Before pusing `i+time`, pop the indexes at the back of the deque whose corresponding value `> A[i+time]`
            b.push_back(i + time);
            if (b.front() < i) b.pop_front(); // Pop index if it's out of window
            if (a.size() == time + 1 && b.size() == time + 1) ans.push_back(i);
        }
        return ans;
    }
};

Solution 2. DP

// OJ: https://leetcode.com/problems/find-good-days-to-rob-the-bank/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    vector<int> goodDaysToRobBank(vector<int>& A, int time) {
        int N = A.size(), left = 1;
        vector<int> right(N, 1), ans;
        for (int i = N - 2; i >= 0; --i) {
            if (A[i] <= A[i + 1]) right[i] += right[i + 1];
        }
        for (int i = 0; i + time < N; ++i) {
            if (i - 1 >= 0 && A[i] <= A[i - 1]) left++;
            else left = 1;
            if (left > time && right[i] > time) ans.push_back(i);
        }
        return ans;
    }
};