Find Good Days to Rob the Bank
Problem 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 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.
Examples:
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.
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.
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 <= 10⁵
- 0 <= security[i], time <= 10⁵
Brute Force Approach
Okay, so here's the thought process:
What comes to mind after reading the problem statement?
For an index i, which represents the ith day, the day is good to rob the bank if there are at least time days before and after it.
Additionally, the number of guards for the time days before the ith day should be in non-increasing order, and the number of guards for the time days after the ith day should be in non-decreasing order.
So, a simple approach that comes to mind is this:
For an index i (or the ith day), first check if the i-time day exists. If it does, go through all the days from i-time to i and verify if the guards are in non-increasing order during these days.
Similarly, check if the i+time day exists. If it does, go through all the days from i to i+time and verify if the guards are in non-decreasing order during these days.
If both these conditions hold true, include the ith day in the answer.
Let's walk through an example:
Let’s perform a dry run for all days (0 to 6) for security = [5,3,3,3,5,6,2] and time = 2
Day 0:
- i-time = -2 (invalid, as it doesn't exist).
- Condition fails due to insufficient preceding days.
- Day 0 is invalid.
Day 1:
- i-time = -1 (invalid, as it doesn't exist).
- Condition fails due to insufficient preceding days.
- Day 1 is invalid.
Day 2:
- i-time = 0, check days [0, 1, 2] for non-increasing:
- 5 >= 3 >= 3 ✅
- i+time = 4, check days [2, 3, 4] for non-decreasing:
- 3 <= 3 <= 5 ✅
- Both conditions satisfied.
- Day 2 is valid.
Day 3:
- i-time = 1, check days [1, 2, 3] for non-increasing:
- 3 >= 3 >= 3 ✅
- i+time = 5, check days [3, 4, 5] for non-decreasing:
- 3 <= 5 <= 6 ✅
- Both conditions satisfied.
- Day 3 is valid.
Day 4:
- i-time = 2, check days [2, 3, 4] for non-increasing:
- 3 >= 3 >= 5 ❌ (fails at 3 < 5).
- Condition fails for the preceding days.
- Day 4 is invalid.
Day 5:
- i-time = 3, check days [3, 4, 5] for non-increasing:
- 3 >= 5 >= 6 ❌ (fails at 3 < 5).
- Condition fails for the preceding days.
- Day 5 is invalid.
Day 6:
- i-time = 4, check days [4, 5, 6] for non-increasing:
- 5 >= 6 >= 2 ❌ (fails at 5 < 6).
- Condition fails for the preceding days.
- Day 6 is invalid.
Final Result:
The valid days to rob the bank are [2, 3].
How to implement it in code:
To implement the brute force approach, follow these steps in code:
- Traverse through a for loop from 0 to n-1 (where n is the length of the array).
- For every index i, check if i-time and i+time are valid (i.e., within bounds).
- If not valid, skip to the next index.
- If valid, check:
- All elements from i-time to i are in non-increasing order.
- All elements from i to i+time are in non-decreasing order.
- If both conditions are satisfied, include the index i in the ans array.
- Finally, return the ans array.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
vector<int> goodDaysToRobBank(vector<int>& security, int time) {
// Size of the security array
int n = security.size();
// Vector to store the result (good days)
vector<int> ans;
// Traverse through each day (index i)
for(int i = 0; i < n; i++)
{
// Check if i-time (left boundary) is valid
int j = i - time;
// If not valid, continue to the next index
if(j < 0)
continue;
// Flag to track if the non-increasing condition is violated
bool flag = 0;
// Check days from i-time to i for non-increasing order
for(; j < i; j++)
{
// If a day violates the non-increasing condition
if(security[j] < security[j + 1])
{
// Mark the condition as violated
flag = 1;
// Exit the loop
break;
}
}
// If the non-increasing condition is violated, continue to the next index
if(flag)
continue;
// Reset the flag for the non-decreasing check
flag = 0;
// Check if i+time (right boundary) is valid
j = i + time;
// If not valid, continue to the next index
if(j >= n)
continue;
// Check days from i to i+time for non-decreasing order
for(; j > i; j--)
{
// If a day violates the non-decreasing condition
if(security[j] < security[j - 1])
{
// Mark the condition as violated
flag = 1;
// Exit the loop
break;
}
}
// If the non-decreasing condition is violated, continue to the next index
if(flag)
continue;
// If both conditions are satisfied, add the index to the result
ans.push_back(i);
}
// Return the list of good days
return ans;
}
};
2. Java Try on Compiler
class Solution {
public List<Integer> goodDaysToRobBank(int[] security, int time) {
// Size of the security array
int n = security.length;
// List to store the result (good days)
List<Integer> ans = new ArrayList<>();
// Traverse through each day (index i)
for (int i = 0; i < n; i++) {
// Check if i-time (left boundary) is valid
int j = i - time;
// If not valid, continue to the next index
if (j < 0)
continue;
// Flag to track if the non-increasing condition is violated
boolean flag = false;
// Check days from i-time to i for non-increasing order
for (; j < i; j++) {
// If a day violates the non-increasing condition
if (security[j] < security[j + 1]) {
// Mark the condition as violated
flag = true;
// Exit the loop
break;
}
}
// If the non-increasing condition is violated, continue to the next index
if (flag)
continue;
// Reset the flag for the non-decreasing check
flag = false;
// Check if i+time (right boundary) is valid
j = i + time;
// If not valid, continue to the next index
if (j >= n)
continue;
// Check days from i to i+time for non-decreasing order
for (; j > i; j--) {
// If a day violates the non-decreasing condition
if (security[j] < security[j - 1]) {
// Mark the condition as violated
flag = true;
// Exit the loop
break;
}
}
// If the non-decreasing condition is violated, continue to the next index
if (flag)
continue;
// If both conditions are satisfied, add the index to the result
ans.add(i);
}
// Return the list of good days
return ans;
}
}
3. Python Try on Compiler
class Solution:
def goodDaysToRobBank(self, security, time):
# Size of the security array
n = len(security)
# List to store the result (good days)
ans = []
# Traverse through each day (index i)
for i in range(n):
# Check if i-time (left boundary) is valid
j = i - time
# If not valid, continue to the next index
if j < 0:
continue
# Flag to track if the non-increasing condition is violated
flag = False
# Check days from i-time to i for non-increasing order
while j < i:
# If a day violates the non-increasing condition
if security[j] < security[j + 1]:
# Mark the condition as violated
flag = True
# Exit the loop
break
j += 1
# If the non-increasing condition is violated, continue to the next index
if flag:
continue
# Reset the flag for the non-decreasing check
flag = False
# Check if i+time (right boundary) is valid
j = i + time
# If not valid, continue to the next index
if j >= n:
continue
# Check days from i to i+time for non-decreasing order
while j > i:
# If a day violates the non-decreasing condition
if security[j] < security[j - 1]:
# Mark the condition as violated
flag = True
# Exit the loop
break
j -= 1
# If the non-decreasing condition is violated, continue to the next index
if flag:
continue
# If both conditions are satisfied, add the index to the result
ans.append(i)
# Return the list of good days
return ans
4. Javascript Try on Compiler
/**
* @param {number[]} security
* @param {number} time
* @return {number[]}
*/
var goodDaysToRobBank = function(security, time) {
// Size of the security array
const n = security.length;
// Array to store the result (good days)
const ans = [];
// Traverse through each day (index i)
for (let i = 0; i < n; i++) {
// Check if i-time (left boundary) is valid
let j = i - time;
// If not valid, continue to the next index
if (j < 0) continue;
// Flag to track if the non-increasing condition is violated
let flag = false;
// Check days from i-time to i for non-increasing order
for (; j < i; j++) {
// If a day violates the non-increasing condition
if (security[j] < security[j + 1]) {
// Mark the condition as violated
flag = true;
// Exit the loop
break;
}
}
// If the non-increasing condition is violated, continue to the next index
if (flag) continue;
// Reset the flag for the non-decreasing check
flag = false;
// Check if i+time (right boundary) is valid
j = i + time;
// If not valid, continue to the next index
if (j >= n) continue;
// Check days from i to i+time for non-decreasing order
for (; j > i; j--) {
// If a day violates the non-decreasing condition
if (security[j] < security[j - 1]) {
// Mark the condition as violated
flag = true;
// Exit the loop
break;
}
}
// If the non-decreasing condition is violated, continue to the next index
if (flag) continue;
// If both conditions are satisfied, add the index to the result
ans.push(i);
}
// Return the list of good days
return ans;
}
Time Complexity: O(n²)
The brute force solution involves iterating through the security array for each index i and performing checks on subsets of the array.
Here's a breakdown of the time complexity:
- The for loop iterates over all indices of the array from 0 to n-1.
This contributes O(n) to the time complexity. - For each index i, the code checks all elements from i-time to i to ensure they are in non-increasing order.
In the worst case, this involves up to time iterations. - Similarly, for each index i, the code checks all elements from i to i+time to ensure they are in non-decreasing order.
This also involves up to time iterations in the worst case. - For each index i, the non-increasing and non-decreasing checks together take O(2 * time) = O(time) time.
- Since the outer loop runs O(n) times, the total time complexity is: O(n * time).
Worst-Case Scenario:
- When time is close to n (e.g., time = n/2):
In this case, the solution would perform O(n * n/2) = O(n²) operations.
Best-Case Scenario:
- When time = 0:
The checks are skipped because no days need to be verified.
In this case, the time complexity is simply O(n).
Space Complexity: O(n)
Auxiliary Space Complexity: O(n)
The solution uses a vector (or array) ans to store the indices of good days.
In the worst case, when every day is a valid good day (e.g., time = 0), and ans will contain all n indices.
This requires O(n) space.
Total Space Complexity: O(n)
The input array security is given, which requires O(n) space.
Adding this to the auxiliary space gives: Total Space = O(n) + O(n) = O(n)
Will Brute Force Work Against the Given Constraints?
For the current solution, the time complexity is O(n²), which is not suitable for n ≤ 10⁵. This means that for each test case, where the size of the array is at most 10⁵, the solution might not execute within the given time limits.
Since O(n²) results in a maximum of 10¹⁰ operations (for n = 10⁵), the solution is not expected to work well for larger test cases. In most competitive programming environments, problems can handle up to 10⁶ operations per test case, meaning that for n ≤ 10⁵, the solution with 10¹⁰ operations is not efficient enough.
When multiple test cases are involved, the total number of operations could easily exceed this limit and approach 10¹⁰ operations, especially when there are many test cases or the value of n increases.
Thus, while the solution meets the time limits for a single test case, the O(n²) time complexity poses a risk for Time Limit Exceeded (TLE) errors when handling larger input sizes or multiple test cases. This can be a challenge for competitive programming problems with larger inputs or numerous test cases.
Can we optimize it?
Yes! There is a better approach to solve this problem.
Curious?
In the previous approach, we checked for every index i that all guards from i-time to i are in non-increasing order and all guards from i to i+time are in non-decreasing order.
This solution takes O(n²) in the worst case because we are checking for every index and traversing from i-time to i and from i to i+time.
Can we reduce it?
Yes, we can.
What if we already know for each index:
- How many indices before it are following the non-increasing order, and
- How many indices after it are following the non-decreasing order?
If we have this information precomputed, we can:
- Simply check for each index if the count of indices satisfying these conditions is greater than or equal to time.
- If so, add the index to our answer.
- Otherwise, move forward.
This approach eliminates the need to recheck the conditions for every index, significantly reducing the time complexity.
How can we do it?
First, we will iterate over the array from the front and calculate how long the non-increasing sequence extends up to each index i. We will store this information for every index in an array.
Next, we will iterate over the array from the back and calculate how long the non-decreasing sequence extends up to each index i. We will store this information for every index in another array.
Finally, we will iterate through the array again and check:
- If the non-increasing sequence length for index i and the non-decreasing sequence length for index i are greater than or equal to time.
- If both conditions are satisfied, we will store the index i in the result array. Otherwise, we will continue to the next index.
This approach ensures that we calculate all the necessary information in linear time, making it much more efficient.
Let's understand with an example:
security = [5, 3, 3, 3, 5, 6, 2], time = 2
Step 1: Calculate Prefix Array (Non-Increasing)
Iterate from left to right, counting how many previous elements form a non-increasing sequence for each index.
prefix[i]: Represents how many indices before index i (inclusive) follow the non-increasing order.
prefix array:
- At index 0: no previous elements → 0
- At index 1: security[1] <= security[0] → 1
- At index 2: security[2] <= security[1] → 2
- At index 3: security[3] <= security[2] → 3
- At index 4: security[4] > security[3] → 0
- At index 5: security[5] > security[4] → 0
- At index 6: security[6] <= security[5] → 1
Result: prefix = [0, 1, 2, 3, 0, 0, 1]
Step 2: Calculate Suffix Array (Non-Decreasing)
Iterate from right to left, counting how many next elements form a non-decreasing sequence for each index.
suffix[i]: Represents how many indices after index i (inclusive) follow the non-decreasing order.
suffix array:
- At index 6: no next elements → 0
- At index 5: security[5] >= security[6] → 1
- At index 4: security[4] <= security[5] → 2
- At index 3: security[3] <= security[4] → 3
- At index 2: security[2] <= security[3] → 4
- At index 1: security[1] <= security[2] → 5
- At index 0: security[0] > security[1] → 0
Result: suffix = [0, 5, 4, 3, 2, 1, 0]
Step 3: Check Conditions
Iterate through the array and check if both conditions are satisfied for each index i:
- prefix[i] >= time
- suffix[i] >= time
- At index 0: prefix[0] = 0, suffix[0] = 0 → Not valid
- At index 1: prefix[1] = 1, suffix[1] = 5 → Not valid
- At index 2: prefix[2] = 2, suffix[2] = 4 → Valid → Add index 2
- At index 3: prefix[3] = 3, suffix[3] = 3 → Valid → Add index 3
- At index 4: prefix[4] = 0, suffix[4] = 2 → Not valid
- At index 5: prefix[5] = 0, suffix[5] = 1 → Not valid
- At index 6: prefix[6] = 1, suffix[6] = 0 → Not valid
Output: [2, 3]
How to code it up?
- Define the size of the security array (n).
- Create two auxiliary arrays, prefix and suffix, of size n, initialized to zero.
- prefix[i] will store the length of the non-increasing sequence ending at index i.
- suffix[i] will store the length of the non-decreasing sequence starting at index i.
- Traverse the security array from left to right (index 1 to n-1).
- For each index, check if the current value is less than or equal to the previous value.
- If true, increment the count based on the value from the previous index in the prefix array.
- Traverse the security array from right to left (index n-2 to 0).
- For each index, check if the current value is less than or equal to the next value.
- If true, increment the count based on the value from the next index in the suffix array.
- Traverse through the security array.
- For each index i, check if:
- prefix[i] >= time
- suffix[i] >= time
- If both conditions are satisfied, add the index to the result list.
- Return the result list containing all indices that satisfy the conditions.
Code Implementation
1. C++ Try on Compiler
class Solution {
public:
// Function to find the good days to rob the bank
vector<int> goodDaysToRobBank(vector<int>& security, int time) {
// Size of the security array
int n = security.size();
// Auxiliary arrays to store the lengths of non-increasing and non-decreasing sequences
vector<int> prefix(n, 0);
vector<int> suffix(n, 0);
// Fill the prefix array (non-increasing sequence)
for(int i = 1; i < n; i++) {
// If current value is less than or equal to the previous value
if(security[i - 1] >= security[i]) {
// Increment the count of non-increasing days
prefix[i] = prefix[i - 1] + 1;
}
}
// Fill the suffix array (non-decreasing sequence)
for(int i = n - 2; i >= 0; i--) {
// If current value is less than or equal to the next value
if(security[i + 1] >= security[i]) {
// Increment the count of non-decreasing days
suffix[i] = suffix[i + 1] + 1;
}
}
// Vector to store the result (good days)
vector<int> ans;
// Check each day to see if it's a good day to rob the bank
for(int i = 0; i < n; i++) {
// If both prefix and suffix conditions are satisfied
if(prefix[i] >= time && suffix[i] >= time) {
// Add the index to the result list
ans.push_back(i);
}
}
// Return the list of good days
return ans;
}
};
2. Java Try on Compiler
class Solution {
// Function to find the good days to rob the bank
public List<Integer> goodDaysToRobBank(int[] security, int time) {
// Size of the security array
int n = security.length;
// Auxiliary arrays to store the lengths of non-increasing and non-decreasing sequences
int[] prefix = new int[n];
int[] suffix = new int[n];
// Fill the prefix array (non-increasing sequence)
for (int i = 1; i < n; i++) {
// If current value is less than or equal to the previous value
if (security[i - 1] >= security[i]) {
// Increment the count of non-increasing days
prefix[i] = prefix[i - 1] + 1;
}
}
// Fill the suffix array (non-decreasing sequence)
for (int i = n - 2; i >= 0; i--) {
// If current value is less than or equal to the next value
if (security[i + 1] >= security[i]) {
// Increment the count of non-decreasing days
suffix[i] = suffix[i + 1] + 1;
}
}
// List to store the result (good days)
List<Integer> ans = new ArrayList<>();
// Check each day to see if it's a good day to rob the bank
for (int i = 0; i < n; i++) {
// If both prefix and suffix conditions are satisfied
if (prefix[i] >= time && suffix[i] >= time) {
// Add the index to the result list
ans.add(i);
}
}
// Return the list of good days
return ans;
}
}
3. Python Try on Compiler
class Solution:
# Function to find the good days to rob the bank
def goodDaysToRobBank(self, security, time):
# Size of the security array
n = len(security)
# Auxiliary arrays to store the lengths of non-increasing and non-decreasing sequences
prefix = [0] * n
suffix = [0] * n
# Fill the prefix array (non-increasing sequence)
for i in range(1, n):
# If current value is less than or equal to the previous value
if security[i - 1] >= security[i]:
# Increment the count of non-increasing days
prefix[i] = prefix[i - 1] + 1
# Fill the suffix array (non-decreasing sequence)
for i in range(n - 2, -1, -1):
# If current value is less than or equal to the next value
if security[i + 1] >= security[i]:
# Increment the count of non-decreasing days
suffix[i] = suffix[i + 1] + 1
# List to store the result (good days)
ans = []
# Check each day to see if it's a good day to rob the bank
for i in range(n):
# If both prefix and suffix conditions are satisfied
if prefix[i] >= time and suffix[i] >= time:
# Add the index to the result list
ans.append(i)
# Return the list of good days
return ans
4. Javascript Try on Compiler
/**
* @param {number[]} security
* @param {number} time
* @return {number[]}
*/
var goodDaysToRobBank = function(security, time) {
// Size of the security array
const n = security.length;
// Auxiliary arrays to store the lengths of non-increasing and non-decreasing sequences
const prefix = new Array(n).fill(0);
const suffix = new Array(n).fill(0);
// Fill the prefix array (non-increasing sequence)
for (let i = 1; i < n; i++) {
// If current value is less than or equal to the previous value
if (security[i - 1] >= security[i]) {
// Increment the count of non-increasing days
prefix[i] = prefix[i - 1] + 1;
}
}
// Fill the suffix array (non-decreasing sequence)
for (let i = n - 2; i >= 0; i--) {
// If current value is less than or equal to the next value
if (security[i + 1] >= security[i]) {
// Increment the count of non-decreasing days
suffix[i] = suffix[i + 1] + 1;
}
}
// Array to store the result (good days)
const ans = [];
// Check each day to see if it's a good day to rob the bank
for (let i = 0; i < n; i++) {
// If both prefix and suffix conditions are satisfied
if (prefix[i] >= time && suffix[i] >= time) {
// Add the index to the result list
ans.push(i);
}
}
// Return the list of good days
return ans;
}
Time Complexity: O(n)
The time complexity of this solution is O(n), where n is the size of the security array. Here's the breakdown:
- Filling the Prefix Array:
- We loop from index 1 to n-1, checking if each element is less than or equal to the previous one, which takes O(n) time.
- Filling the Suffix Array:
- We loop from index n-2 to 0, checking if each element is less than or equal to the next one, which also takes O(n) time.
- Checking for Good Days:
- We loop through the array once more to check if both the prefix and suffix conditions are met for each day, which takes O(n) time.
Thus, the overall time complexity is O(n).
Space Complexity: O(n)
- Auxiliary Space Complexity: O(n)
The only additional space used is for the prefix and suffix arrays, both of size n.
Therefore, the auxiliary space complexity is O(n). - Total Space Complexity: O(n)
The input is the security array, which requires O(n) space. We also use three arrays: prefix, suffix, and ans, each of size n.
Thus, the total space complexity is O(n) for the input array plus O(n) for the three additional arrays. Therefore, the total space complexity is O(n).