Find Good Days to Rob the Bank
MedPrompt
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
timedays before and after theithday, - The number of guards at the bank for the
timedays beforeiare non-increasing, and - The number of guards at the bank for the
timedays afteriare 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 <= 1050 <= security[i], time <= 105
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code. We iterate through each day that could potentially be a good day to rob the bank. A day i is a potential candidate only if there are at least time days before it and time days after it. This means we only need to check days i in the range [time, n - 1 - time], where n is the total number of days.
Algorithm
- Initialize an empty list
goodDaysto store the result. - Let
nbe the length of thesecurityarray. - Iterate through each day
ifromtimeton - 1 - time. These are the only days that can havetimedays before and after them. - For each candidate day
i, assume it's a good day and check the two conditions:- Before
i: Check ifsecurity[j] >= security[j+1]for alljfromi - timeup toi - 1. If this condition is ever violated, dayiis not good, and we can move to the next dayi+1. - After
i: If the first condition holds, check ifsecurity[j] <= security[j+1]for alljfromiup toi + time - 1. If this condition is violated, dayiis not good.
- Before
- If both conditions are met for day
i, addito thegoodDayslist. - After checking all possible days, return the
goodDayslist.
Walkthrough
For each candidate day i, we perform two separate checks:
- Non-increasing before: We check if the number of guards is non-increasing for
timedays leading up to and including dayi. This involves a loop fromi - timetoi - 1, verifying thatsecurity[j] >= security[j+1]for eachj. - Non-decreasing after: We check if the number of guards is non-decreasing for
timedays starting from dayi. This involves another loop fromitoi + time - 1, verifying thatsecurity[j] <= security[j+1]for eachj. If both conditions are satisfied, we add the dayito our list of good days.
import java.util.ArrayList;import java.util.List; class Solution { public List<Integer> goodDaysToRobBank(int[] security, int time) { List<Integer> goodDays = new ArrayList<>(); int n = security.length; // Iterate through all possible good days for (int i = time; i < n - time; i++) { boolean nonIncreasingBefore = true; // Check for non-increasing sequence of 'time' days before day i for (int j = 1; j <= time; j++) { if (security[i - j] < security[i - j + 1]) { nonIncreasingBefore = false; break; } } if (nonIncreasingBefore) { boolean nonDecreasingAfter = true; // Check for non-decreasing sequence of 'time' days after day i for (int j = 1; j <= time; j++) { if (security[i + j - 1] > security[i + j]) { nonDecreasingAfter = false; break; } } if (nonDecreasingAfter) { goodDays.add(i); } } } return goodDays; }}Complexity
Time
O(n * time). The outer loop runs for `n - 2 * time` iterations. Inside it, there are two loops, each running up to `time` times. This results in a total time complexity of `O((n - 2*time) * 2*time)`, which simplifies to `O(n * time)`.
Space
O(1) extra space. The space used for the output list can be up to O(n) in the worst case, but this is often excluded from space complexity analysis.
Trade-offs
Pros
Simple to understand and implement as it directly follows the problem's definition.
Low space complexity if the output list is not considered.
Cons
Highly inefficient for large inputs, especially when
timeis large. TheO(n * time)complexity can lead to a 'Time Limit Exceeded' error on competitive programming platforms.It performs a lot of redundant computations. For example, when checking day
iand dayi+1, the check for the overlapping window of days is performed twice.
Solutions
Solution
class Solution {public List<Integer> goodDaysToRobBank(int[] security, int time) { int n = security.length; if (n <= time * 2) { return Collections.emptyList(); } int[] left = new int[n]; int[] right = new int[n]; for (int i = 1; i < n; ++i) { if (security[i] <= security[i - 1]) { left[i] = left[i - 1] + 1; } } for (int i = n - 2; i >= 0; --i) { if (security[i] <= security[i + 1]) { right[i] = right[i + 1] + 1; } } List<Integer> ans = new ArrayList<>(); for (int i = time; i < n - time; ++i) { if (time <= Math.min(left[i], right[i])) { ans.add(i); } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.