2100. 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.

• deque solution

class Solution {
    bool bigger(vector<int>& A, deque<int>& dq, int i) {
        if(dq.back() == i and dq.size() == 1) return false;
        return A[dq[dq.size() - 2]] > A[i];
    }
public:
    vector<int> goodDaysToRobBank(vector<int>& A, int time) {
        deque<int> inc, dec;
        vector<int> res;

        int n = A.size();

        for(int i = 0; i < n; i++) {
            if(!dec.empty() and A[dec.back()] < A[i]) dec.clear();
            dec.push_back(i);
            if(!dec.empty() and dec[0] + time == i) {
                dec.pop_front();
                inc.push_back(i);
            }
            
            if(!inc.empty() and inc.front() + time == i and (time == 0 or A[i - 1] <= A[i])) {
                res.push_back(inc.front());
                inc.pop_front();
            } else if(!inc.empty() and i and A[i - 1] > A[i]) {
                while(!inc.empty() and inc.front() != i) {
                    inc.pop_front();
                }
            }
        }

        return res;
    }
};

• prefix array suffix array solution

class Solution {
public:
    vector<int> goodDaysToRobBank(vector<int>& A, int time) {
        int n = A.size();
        vector<int> res, pre(n, 1), suf(n, 1);
        
        for(int i = 1, cnt = 1; i < n; i++) {
            if(A[i - 1] >= A[i]) cnt++;
            else cnt = 1;
            pre[i] = cnt;
        }
        
        for(int i = n - 2, cnt = 1; i >= 0; i--) {
            if(A[i + 1] >= A[i]) cnt++;
            else cnt = 1;
            suf[i] = cnt;
        }
        
        for(int i = 0; i < n; i++) {
            if(pre[i] - 1 >= time and suf[i] - 1 >= time)
                res.push_back(i);
        }

        return res;
    }
};