Skip to main content
Talentd

Find All Good Indices - Solution & Explanation

MediumArrayDynamic ProgrammingPrefix Sum10 min readAsked at: Goldman Sachs
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 106
  • 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.

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.

Code

PythonC

Python

C

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.

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.

Code

JavaJavaScript

Java

JavaScript

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

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

Video Solution

Leetcode 2420 Find All Good Indices | Coding Decoded SDE Sheet • Coding Decoded • 2,405 views views

Watch 9 more video solutions →

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).

Ready to solve this problem?

Practice Find All Good Indices with our built-in code editor and test cases.

Practice on FleetCode
Previous

Abbreviating the Product of a Range

Next

Count the Number of K-Big Indices