#2420

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Find All Good Indices

Identify all indices in an array where the k-length prefix is non-increasing and the k-length suffix is non-decreasing.

Problem Statement

Given a 0-indexed integer array nums of size n and a positive integer k, an index i is called good if the k elements before i are non-increasing and the k elements after i are non-decreasing. Return all good indices sorted in increasing order.

For each index i where k <= i < n - k, check whether nums[i - k : i] is non-increasing and nums[i + 1 : i + k + 1] is non-decreasing. Collect all such indices into an array and return it.

Examples

Example 1

Input: nums = [2,1,1,1,3,4,1], k = 2

Output: [2,3]

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: []

There are no good indices in this array.

Constraints

n == nums.length
3 <= n <= 105
1 <= nums[i] <= 106
1 <= k <= n / 2

Solution Approach

Precompute Non-Increasing Prefixes

Iterate from left to right and for each position store the length of the current non-increasing sequence ending at that index. This allows O(1) checking whether a prefix of length k is non-increasing for any candidate index i.

Precompute Non-Decreasing Suffixes

Iterate from right to left and store the length of the non-decreasing sequence starting at each index. With this array, you can instantly verify if the k-length suffix after index i meets the non-decreasing condition.

Collect Good Indices

Scan through indices k to n - k - 1. For each index, check the precomputed prefix and suffix lengths to determine if both conditions are satisfied. Append valid indices to the result array in order.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) because each element is visited once during prefix and suffix precomputations and once during the final scan. Space complexity is O(n) for storing prefix and suffix arrays.

What Interviewers Usually Probe

Candidate recognizes the pattern of using state transition dynamic programming for prefix and suffix computations.
Candidate correctly handles edge indices where k-length prefix or suffix may not exist.
Candidate produces a solution with linear time instead of checking all subarrays naively.

Common Pitfalls or Variants

Common pitfalls

Forgetting that the prefix or suffix must be exactly k elements and miscounting the lengths.
Using nested loops to check each subarray, causing TLE for large n.
Incorrectly handling non-increasing or non-decreasing conditions when consecutive equal elements appear.

Follow-up variants

Find all indices where prefix is strictly decreasing and suffix is strictly increasing.
Determine good indices for k-length non-increasing and non-decreasing segments in a circular array.
Compute the maximum number of good indices for a varying k value instead of a fixed k.

FAQ

What is the main strategy for Find All Good Indices?

Use state transition dynamic programming to precompute non-increasing prefixes and non-decreasing suffixes, then scan for indices satisfying both conditions.

Can this be solved without extra space?

Yes, but it complicates checking previous and next k elements; the DP arrays provide clearer O(n) solution.

How do you handle equal consecutive elements?

Equal elements count as non-increasing or non-decreasing, so include them when computing prefix and suffix lengths.

What is the time complexity for large arrays?

With prefix and suffix precomputation, the algorithm runs in O(n) time, suitable for n up to 10^5.

Why is this pattern called state transition dynamic programming?

Because each element's prefix or suffix length depends on the previous element's state, forming a chain of transitions.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def goodIndices(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        decr = [1] * (n + 1)
        incr = [1] * (n + 1)
        for i in range(2, n - 1):
            if nums[i - 1] <= nums[i - 2]:
                decr[i] = decr[i - 1] + 1
        for i in range(n - 3, -1, -1):
            if nums[i + 1] <= nums[i + 2]:
                incr[i] = incr[i + 1] + 1
        return [i for i in range(k, n - k) if decr[i] >= k and incr[i] >= k]

Continue Practicing

#2439 minimize maximum of array #2552 count increasing quadruplets #2218 maximum value of k coins from piles