Find Good Days to Rob the Bank - Practice Coding Problems

Find Good Days to Rob the Bank - Problem

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.

Input & Output

Example 1 — Basic Case

$ Input: security = [5,3,3,3,5,6,2], time = 2

› Output: [2,3]

💡 Note: Day 2: security[0:3] = [5,3,3] is non-increasing, security[2:5] = [3,3,5] is non-decreasing. Day 3: security[1:4] = [3,3,3] is non-increasing, security[3:6] = [3,5,6] is non-decreasing.

Example 2 — No Valid Days

$ Input: security = [1,1,1,1,1], time = 0

› Output: [0,1,2,3,4]

💡 Note: When time=0, we only need 0 days before and after, so every day is valid since there are no additional constraints to check.

Example 3 — Array Too Small

$ Input: security = [1,2,3,4,5,6], time = 2

› Output: []

💡 Note: For time=2, we need at least 2+1+2=5 days, but checking each position: no position satisfies both non-increasing before and non-decreasing after conditions.

Constraints

1 ≤ security.length ≤ 10⁵
0 ≤ time ≤ security.length
1 ≤ security[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Security array [5,3,3,3,5,6,2] with time=2

Check Pattern

Find days with non-increasing before and non-decreasing after

Output

Return indices [2,3] of valid robbery days

Key Takeaway

🎯 Key Insight: Use prefix arrays to pre-compute sequence patterns for O(1) validation per day

Asked in

a Amazon 15 f Facebook 8

The key insight is to pre-compute consecutive non-increasing and non-decreasing sequences using prefix arrays. Instead of checking each day's neighbors repeatedly, we build two arrays that store sequence lengths ending/starting at each position. Best approach uses prefix arrays with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Arrays Optimization	O(n)	O(n)	Pre-compute non-increasing and non-decreasing sequences for O(1) lookups
Brute Force	O(n × time)	O(1)	Check each day by examining all required days before and after

Prefix Arrays Optimization — Algorithm Steps

Build prefix array for non-increasing sequences going backwards
Build prefix array for non-decreasing sequences going forwards
For each day, check if both prefix values >= time
Collect all valid days

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Before Array

Count non-increasing sequences ending at each position

Build After Array

Count non-decreasing sequences starting at each position

Check Conditions

Find days where both arrays have value >= time

Collect Results

Return all valid days

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* security, int securitySize, int time, int* returnSize) {
    int* result = (int*)malloc(securitySize * sizeof(int));
    *returnSize = 0;
    
    if (securitySize < 2 * time + 1) return result;
    
    // Build prefix arrays
    int* nonIncreasingBefore = (int*)calloc(securitySize, sizeof(int));
    int* nonDecreasingAfter = (int*)calloc(securitySize, sizeof(int));
    
    // Count consecutive non-increasing days before each position
    for (int i = 1; i < securitySize; i++) {
        if (security[i] <= security[i - 1]) {
            nonIncreasingBefore[i] = nonIncreasingBefore[i - 1] + 1;
        }
    }
    
    // Count consecutive non-decreasing days after each position
    for (int i = securitySize - 2; i >= 0; i--) {
        if (security[i] <= security[i + 1]) {
            nonDecreasingAfter[i] = nonDecreasingAfter[i + 1] + 1;
        }
    }
    
    for (int i = time; i < securitySize - time; i++) {
        if (nonIncreasingBefore[i] >= time && nonDecreasingAfter[i] >= time) {
            result[(*returnSize)++] = i;
        }
    }
    
    free(nonIncreasingBefore);
    free(nonDecreasingAfter);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int security[1000];
    int securitySize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        int val = atoi(token);
        if (val != 0 || token[0] == '0') {
            security[securitySize++] = val;
        }
        token = strtok(NULL, "[,]");
    }
    
    int time;
    scanf("%d", &time);
    
    int returnSize;
    int* result = solution(security, securitySize, time, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Three passes through array: two to build prefix arrays, one to check results

✓ Linear Growth

Space Complexity

O(n)

Two prefix arrays of size n to store consecutive sequence lengths

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Arrays Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler