DSA SheetMedium
EditorialPractice

PREFIX SUM › PREFIX SUM

Find Good Days to Rob the Bank

MediumEditorial · 6 minGenerated by gpt-5.6-luna · Aug 29

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionturning both sides of a day into local run lengths

A day i is valid only when two independent conditions meet at the same index. Looking left from i, guard counts must never increase as you approach i. Looking right from i, guard counts must never decrease as you move away from i. The day also needs time positions on each side, so the two conditions can only matter for indices from time through n - time - 1.

For every index, store how many consecutive comparisons succeed on its left and how many succeed on its right. The left count grows when security[i] <= security[i - 1]; otherwise the non-increasing run stops. The right count grows when security[i] <= security[i + 1], computed from right to left. A day is good exactly when both stored counts are at least time.

Approachtwo directional passes and one final filter

  1. Let n be the number of days and create left and right arrays filled with zero. Zero means no valid comparison has been established yet, which correctly handles the boundaries.
  2. Scan from index 1 to n - 1 and extend left[i] from left[i - 1] when security[i] <= security[i - 1]. If the comparison fails, leave left[i] at zero because the required non-increasing run ends immediately before i.
  3. Scan from index n - 2 down to zero and extend right[i] from right[i + 1] when security[i] <= security[i + 1]. The reverse direction is necessary because right[i] depends on the already computed value to its right.
  4. Inspect only indices i from time through n - time - 1. These are the only indices with at least time positions available on both sides, so checking outside this range could accept a day that does not have enough surrounding days.
  5. Append i when left[i] >= time and right[i] >= time. Each count records successful adjacent comparisons, and time comparisons create exactly time neighboring days, so the two thresholds match the definition directly.
  6. Return the collected indices without sorting them. The final scan already visits them in increasing order, and the problem accepts any order.

Complexitylinear work with arrays of directional run lengths

MEASUREBOUNDWHY
TimeO(n)The left pass, right pass, and final scan each inspect every index at most once. Their costs add to three linear scans, so no index causes repeated expansion of a run.
SpaceO(n) extraThe left and right arrays each contain n counts, and the answer is required output rather than working memory. The extra space remains O(n) for every input shape because the two arrays are allocated by length, even when every comparison fails.
Here n is the number of days in security. The returned answer is required output and is excluded from the extra-space bound.

Annotated solutionC++ · two directional passes · complete judge-ready implementation

CPPStore the left and right run lengths, then filter indices whose two counts reach time.
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> goodDaysToRobBank(vector<int>& security, int time) {
        int n = security.size();
        vector<int> left(n, 0), right(n, 0);

        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;
            }
        }

        vector<int> ans;
        for (int i = time; i < n - time; ++i) {
            if (left[i] >= time && right[i] >= time) {
                ans.push_back(i);
            }
        }

        return ans;
    }
};

The initialization to zero is doing more than setting defaults. At index i, left[i] counts comparisons ending at i, so the first possible comparison begins at index 1. Similarly, right[i] counts comparisons beginning at i, so the last possible comparison is at index n - 2. The final loop's bounds handle the separate requirement that enough actual days exist on both sides.

Common mistakestwo comparisons that look similar but point in opposite directions

Previous · Minimum Penalty for a Shop