Find All Good Indices — Editorial

Opening the reading…

Intuitioneach side of an index can be summarized by one run length

For an index i to be good, the k values ending at i - 1 must never increase as you move right, and the k values starting at i + 1 must never decrease as you move right. The value at i itself does not participate in either condition, so the two checks are deliberately separated around it.

For every position, record how long the current non-increasing run has continued from the left. Do the same from the right for non-decreasing runs. Then index i is good exactly when the run ending at i - 1 has length at least k and the run starting at i + 1 has length at least k. Each condition becomes a constant-time lookup instead of a scan.

Approachbuild both directional summaries before checking candidates

Create left and right arrays filled with 1, because a single element is always a valid run and this gives every position a meaningful base length.

Scan from left to right and extend left[i] from left[i - 1] when nums[i] <= nums[i - 1]; otherwise reset it to 1, because an increase breaks the non-increasing run at i.

Scan from right to left and extend right[i] from right[i + 1] when nums[i] <= nums[i + 1]; otherwise reset it to 1, because a decrease while moving right breaks the non-decreasing suffix.

Visit only indices from k through n - k - 1, because every other index does not have k elements on both sides and cannot be good.

For each candidate i, test left[i - 1] >= k and right[i + 1] >= k, because those entries describe exactly the k elements immediately before and after i.

Append every passing index in this increasing scan order, so the returned list is already sorted and needs no final sorting pass.

Complexitytwo linear passes and two linear summaries

MEASURE	BOUND	WHY
Time	O(n)	The left and right passes each compare neighboring elements once, and the candidate scan examines each index at most once. The work is therefore a constant number of visits per array position, with no candidate rescanning a window.
Space	O(n) extra	The left and right run arrays each use O(n) working memory. The returned answer is required output and is excluded from this bound. This remains O(n) in the worst input shape because the summaries store one value for every position.

Here n is the number of elements in nums.

Annotated solutionC++ · two directional passes · constant-time candidate checks

CPPCompute left and right run lengths, then test every index with enough room on both sides.

#include <vector>

using namespace std;

class Solution {
public:
    vector<int> goodIndices(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> left(n, 1), right(n, 1);

        for (int i = 1; i < n; ++i) {
            if (nums[i] <= nums[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }

        for (int i = n - 2; i >= 0; --i) {
            if (nums[i] <= nums[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
        }

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

        return ans;
    }
};

The two neighboring comparisons use <= in both passes, but their meanings differ because the scan directions differ. In the left-to-right pass, nums[i] <= nums[i - 1] means the sequence has not increased. In the right-to-left pass, nums[i] <= nums[i + 1] means the sequence will not decrease when read from left to right.