2420. Find All Good Indices - Solution Guide

The problem

You are given a 0-indexed integer array nums of size n and a positive integer k.

We call an index i in the range k <= i < n - k good if the following conditions are satisfied:

The k elements that are just before the index i are in non-increasing order.
The k elements that are just after the index i are in non-decreasing order.

Return an array of all good indices sorted in increasing order.

Example 1:

Input: nums = [2,1,1,1,3,4,1], k = 2
Output: [2,3]
Explanation: There are two good indices in the array:
- Index 2. The subarray [2,1] is in non-increasing order, and the subarray [1,3] is in non-decreasing order.
- Index 3. The subarray [1,1] is in non-increasing order, and the subarray [3,4] is in non-decreasing order.
Note that the index 4 is not good because [4,1] is not non-decreasing.

Example 2:

Input: nums = [2,1,1,2], k = 2
Output: []
Explanation: There are no good indices in this array.

Constraints:

n == nums.length
3 <= n <= 10⁵
1 <= nums[i] <= 10⁶
1 <= k <= n / 2

Approach overview

Problem Overview: Given an integer array nums and an integer k, return all indices i where the previous k elements form a non-increasing sequence and the next k elements form a non-decreasing sequence. Only indices with at least k elements on both sides qualify.

Approach 1: Pre-calculated Arrays for Monotonic Subarrays (O(n) time, O(n) space)

The key observation: instead of rechecking monotonicity around every index, precompute it once. Build two arrays while iterating through the input. The first array stores how long the current non-increasing streak continues up to each index. The second stores how long the non-decreasing streak continues starting from each index when traversing from right to left. Once these arrays are filled, iterate through valid indices and check dec[i-1] >= k and inc[i+1] >= k. This avoids repeatedly scanning subarrays and reduces the solution to linear time. The technique resembles prefix-style preprocessing commonly used in array and dynamic programming problems where previous computations are reused.

Each pass over the array performs constant work, so the total runtime is O(n). Two auxiliary arrays of size n store the monotonic lengths, giving O(n) space complexity. This approach is straightforward, cache-friendly, and easy to reason about during interviews.

Approach 2: Sliding Window with Monotonic Checks (O(n) time, O(1) extra space)

Another option tracks monotonic violations while sliding windows of size k. Maintain counters representing how many positions break the non-increasing condition on the left window and how many break the non-decreasing condition on the right window. As the index moves forward, update the counters by removing the outgoing comparison and adding the new one. When both counters are zero, the current index satisfies the requirement. This technique avoids storing auxiliary arrays and processes the array in a single pass.

The sliding window pattern is common in array processing where constraints apply to fixed-size ranges. Each step updates only a few comparisons, so runtime stays O(n) with O(1) additional memory. Conceptually it resembles maintaining prefix-style validity information, similar to ideas used in prefix sum based preprocessing.

Recommended for interviews: The pre-calculated arrays approach is what most interviewers expect. It clearly shows you recognized the monotonic subarray structure and optimized repeated checks using preprocessing. Mentioning the brute-force idea first (checking each index with two loops) demonstrates problem understanding, but implementing the O(n) preprocessing solution shows strong algorithmic thinking.

Approach 1: Use Pre-calculated Arrays for Monotonic Subarrays

This approach involves creating two auxiliary arrays to determine non-increasing and non-decreasing sequences.

We maintain two arrays, nonInc and nonDec to keep track of whether a sequence of length k is non-increasing or non-decreasing respectively:

nonInc[i] indicates whether elements upto and including i (from the left) form a non-increasing sequence of length k.
nonDec[i] indicates whether elements from i onwards form a non-decreasing sequence of length k.

We first populate these arrays and then iterate over potential good indices to validate both conditions based on precomputed results.

Python

def goodIndices(nums, k):
    n = len(nums)
    nonInc = [0] * n
    nonDec = [0] * n

    for i in range(n):
        nonInc[i] = 0 if i == 0 else nonInc[i-1]
        if i > 0 and nums[i-1] >= nums[i]:
            nonInc[i] += 1

    for i in range(n-1, -1, -1):
        nonDec[i] = 0 if i == n-1 else nonDec[i+1]
        if i < n-1 and nums[i] <= nums[i+1]:
            nonDec[i] += 1

    good_indicies = []
    for i in range(k, n-k):
        if nonInc[i-1] >= k and nonDec[i+1] >= k:
            good_indicies.append(i)

    return good_indicies

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

int* goodIndices(int* nums, int numsSize, int k, int* returnSize) {
    int* nonInc = (int*)calloc(numsSize, sizeof(int));
    int* nonDec = (int*)calloc(numsSize, sizeof(int));
    int* result = (int*)malloc(numsSize * sizeof(int));
    *returnSize = 0;

    for(int i = 1; i < numsSize; i++) {
        if(nums[i-1] >= nums[i]) nonInc[i] = nonInc[i-1] + 1;
    }

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

    for(int i = k; i < numsSize-k; i++) {
        if(nonInc[i-1] >= k && nonDec[i+1] >= k) {
            result[(*returnSize)++] = i;
        }
    }

    free(nonInc);
    free(nonDec);
    return result;
}

The solution defines two supplementary arrays, nonInc and nonDec, which are built up over single traversals of the input list. This allows us to efficiently ascertain whether each candidate index meets the necessary non-increasing and non-decreasing conditions.

Complexity

Time Complexity: O(n), where n is the length of the array.

Space Complexity: O(n) due to the auxiliary arrays.

Try this approach in the editor

Approach 2: Sliding Window Technique

The sliding window technique dynamically tracks conditions over subarrays of interest to determine valid good indices. By adjusting pointers, the solution keeps track of non-increasing and non-decreasing windows of k.

Update window constraints on movement and validate the conditions without reconstructing entire subarrays.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static List<Integer> goodIndices(int[] nums, int k) {
        int n = nums.length;
        int[] nonInc = new int[n];
        int[] nonDec = new int[n];
        List<Integer> result = new ArrayList<>();

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

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

        for (int i = k; i < n - k; i++) {
            if (nonInc[i - 1] >= k && nonDec[i + 1] >= k) {
                result.add(i);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {2,1,1,1,3,4,1};
        int k = 2;
        System.out.println(goodIndices(nums, k)); // Output: [2, 3]
    }
}

JavaScript

function goodIndices(nums, k) {
    const n = nums.length;
    const nonInc = Array(n).fill(0);
    const nonDec = Array(n).fill(0);
    const result = [];

    for (let i = 1; i < n; i++) {
        if (nums[i - 1] >= nums[i]) nonInc[i] = nonInc[i - 1] + 1;
    }

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

    for (let i = k; i < n - k; i++) {
        if (nonInc[i - 1] >= k && nonDec[i + 1] >= k) result.push(i);
    }

    return result;
}

console.log(goodIndices([2, 1, 1, 1, 3, 4, 1], 2)); // Output: [2, 3]

In the Java implementation, non-increasing and non-decreasing status is tracked in-prefix to maintain O(n) confirmations over potential good indices. Good index validation avoids redundant or overlapping evaluations of subarray elements.

Complexity

Time Complexity: O(n)
Space Complexity: O(1) for extra space (output list is returned).

Try this approach in the editor

Approach 3: Recursion

We define two arrays decr and incr, which represent the longest non-increasing and non-decreasing subarray lengths from left to right and from right to left, respectively.

We traverse the array, updating the decr and incr arrays.

Then we sequentially traverse the index i (where k\le i \lt n - k), if decr[i] geq k and incr[i] geq k, then i is a good index.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array.

C++

class Solution {
public:
    vector<int> goodIndices(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> decr(n, 1);
        vector<int> incr(n, 1);
        for (int i = 2; i < n; ++i) {
            if (nums[i - 1] <= nums[i - 2]) {
                decr[i] = decr[i - 1] + 1;
            }
        }
        for (int i = n - 3; ~i; --i) {
            if (nums[i + 1] <= nums[i + 2]) {
                incr[i] = incr[i + 1] + 1;
            }
        }
        vector<int> ans;
        for (int i = k; i < n - k; ++i) {
            if (decr[i] >= k && incr[i] >= k) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

func goodIndices(nums []int, k int) []int {
	n := len(nums)
	decr := make([]int, n)
	incr := make([]int, n)
	for i := range decr {
		decr[i] = 1
		incr[i] = 1
	}
	for i := 2; i < n; i++ {
		if nums[i-1] <= nums[i-2] {
			decr[i] = decr[i-1] + 1
		}
	}
	for i := n - 3; i >= 0; i-- {
		if nums[i+1] <= nums[i+2] {
			incr[i] = incr[i+1] + 1
		}
	}
	ans := []int{}
	for i := k; i < n-k; i++ {
		if decr[i] >= k && incr[i] >= k {
			ans = append(ans, i)
		}
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Use Pre-calculated Arrays for Monotonic Subarrays	Time Complexity: O(n), where n is the length of the array. Space Complexity: O(n) due to the auxiliary arrays.
Sliding Window Technique	Time Complexity: O(n) Space Complexity: O(1) for extra space (output list is returned).
Recursion	–

Approach

Complexity

Use Pre-calculated Arrays for Monotonic Subarrays

Time Complexity: O(n), where n is the length of the array.

Space Complexity: O(n) due to the auxiliary arrays.

Sliding Window Technique

Time Complexity: O(n)
Space Complexity: O(1) for extra space (output list is returned).

Recursion

–

Complexity analysis

Approach	Time	Space	When to Use
Pre-calculated Monotonic Arrays	O(n)	O(n)	Most common interview solution. Simple preprocessing and easy correctness reasoning.
Sliding Window Technique	O(n)	O(1)	When memory usage matters or when practicing window-based array processing.

Frequently asked questions

Is Find All Good Indices easy or hard?

Find All Good Indices is considered a Medium difficulty problem. The challenge comes from recognizing that repeatedly checking subarrays leads to O(n*k) time, while preprocessing monotonic segments reduces the problem to linear time.

Find All Good Indices Python/Java solution

In Python or Java, implement two passes that build arrays tracking non-increasing and non-decreasing streaks. After preprocessing, iterate through candidate indices and append those that satisfy both conditions. The implementation remains O(n) time and O(n) space in both languages.

How to solve Find All Good Indices in O(n)?

Precompute monotonic subarray lengths. Traverse left to right to record how long each non-increasing sequence lasts, then traverse right to left to record non-decreasing sequences. For each index i between k and n-k-1, check whether the left streak at i-1 and the right streak at i+1 are at least k.

What is the best approach for Find All Good Indices?

The most common solution precomputes two arrays that track monotonic streak lengths. One array stores the length of non-increasing sequences ending at each index, and the other stores non-decreasing sequences starting at each index. After preprocessing, each index can be validated in O(1), giving an overall time complexity of O(n) with O(n) extra space.

Is Find All Good Indices asked at Google/Amazon/Meta?

Problems involving monotonic arrays, preprocessing, and sliding window checks appear frequently in interviews at companies like Google, Amazon, and Meta. Variations of this pattern show up in array validation and range-condition problems.

What data structure is used in Find All Good Indices?

The core solution uses simple arrays to store precomputed monotonic sequence lengths. No advanced data structures are required. The algorithm relies mainly on array traversal, dynamic programming style state reuse, and optional sliding window counters.

What is the time complexity of Find All Good Indices?

The optimal solution runs in O(n) time. The algorithm performs two preprocessing passes to compute monotonic lengths and a final pass to collect valid indices. Space complexity is O(n) for the auxiliary arrays, though a sliding window variant can reduce extra space to O(1).

Find All Good Indices solution and explanation

The problem

Approach overview

Approach 1: Use Pre-calculated Arrays for Monotonic Subarrays

Approach 2: Sliding Window Technique

Approach 3: Recursion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find All Good Indices solution and explanation

The problem

Approach overview

Approach 1: Use Pre-calculated Arrays for Monotonic Subarrays

Approach 2: Sliding Window Technique

Approach 3: Recursion

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems