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:
k elements that are just before the index i are in non-increasing order.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.length3 <= n <= 1051 <= nums[i] <= 1061 <= k <= n / 2Problem 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.
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.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n) due to the auxiliary arrays.
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.
Java
JavaScript
Time Complexity: O(n)
Space Complexity: O(1) for extra space (output list is returned).
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.
| 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) |
| Recursion | — |
| 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. |
Leetcode 2420 Find All Good Indices | Coding Decoded SDE Sheet • Coding Decoded • 2,357 views views
Watch 9 more video solutions →Practice Find All Good Indices with our built-in code editor and test cases.
Practice on FleetCode