I came across the LeetCode problem 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 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.

The solution, that I created seems fine to me. Not sure, where I am going wrong with some test cases failing.

class Solution(object):
    def goodDaysToRobBank(self, security, time):
        """
        :type security: List[int]
        :type time: int
        :rtype: List[int]
        """
        total_guards = len(security)
        if time == 0:
            return [i for i in range(total_guards)]
        
        left = [1]*total_guards
        right = [1]*total_guards
        l_pattern_found = False
        r_pattern_found = False
        
        for i in range(1, total_guards):
            if security[i-1] >= security[i]:
                left[i] = left[i-1]   1
                l_pattern_found = True

                
        for i in range(total_guards-2, -1, -1):
            if security[i 1] >= security[i]:
                right[i] = right[i 1]   1
                r_pattern_found = True

            
        if not l_pattern_found or not r_pattern_found:
            return []
        
        days = []
        for i in range(time, total_guards-time):
            if left[i-1] >= time and right[i 1] >= time:
                days.append(i)
                
        return days
    

Here is what I have done:

• Compute the left prefix for the condition mentioned
• Compute the right prefix for the condition mentioned
• Find the days in the range [time, n-time]

This is failing for the test case as follows:

security = [1,2,5,4,1,0,2,4,5,3,1,2,4,3,2,4,8]
time = 2

The expected output is: [5,10,14] and my output is [4,5,6,10,14]

What is it that I am doing wrong?

CodePudding user response：

The main issue is in this line:

        if left[i-1] >= time and right[i 1] >= time:

Here the value of left[i-1] does not guarantee that the current value at security[i] is not greater than security[i-1]. To ensure that, you would need to look at left[i] instead of left[i-1]. For the same reason you should be looking at right[i] instead of right[i 1]. But that means you need to reduce all counts by 1, and initialise your left and right lists with zeroes:

    left = [0]*total_guards
    right = [0]*total_guards

With those corrections it will work.