# Find All Good Indices
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-all-good-indices)
Canonical: https://scaleengineer.com/dsa/problems/find-all-good-indices
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs)
---
## 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 <= 105`
* `1 <= nums[i] <= 106`
* `1 <= k <= n / 2`

# Approaches
## Brute Force Iteration
The most straightforward approach is to iterate through every possible index `i` that could be a 'good' index and, for each one, verify if it meets the two specified conditions directly by checking the subarrays before and after it.
**Time:** O(n * k), where n is the number of elements in `nums`. For each of the `n - 2k` potential indices, we perform two separate checks, each taking O(k) time. This can lead to a Time Limit Exceeded error for large inputs. · **Space:** O(1) if we don't count the output list. The space required for the result list can be up to O(n) in the worst case.
**Pros:** Simple to understand and implement.
**Cons:** Inefficient due to redundant computations of checking subarray properties.; Likely to time out on larger test cases.
### Explanation
We can loop through all indices `i` from `k` to `n - k - 1`. For each `i`, we perform two separate checks:
1.  **Check Before:** We check if the subarray `nums[i-k...i-1]` is non-increasing. This is done by iterating from `j = i-k` to `i-2` and ensuring `nums[j] >= nums[j+1]` for all `j`.
2.  **Check After:** If the first condition holds, we check if the subarray `nums[i+1...i+k]` is non-decreasing. This is done by iterating from `j = i+1` to `i+k-1` and ensuring `nums[j] <= nums[j+1]` for all `j`.

If both conditions are satisfied, we add the index `i` to our result list. Since we iterate through `i` in increasing order, the final list will also be sorted.

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

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

        // Iterate through all possible good indices
        for (int i = k; i < n - k; i++) {
            // Check the k elements before index i
            boolean isNonIncreasing = true;
            for (int j = i - k; j < i - 1; j++) {
                if (nums[j] < nums[j + 1]) {
                    isNonIncreasing = false;
                    break;
                }
            }

            if (isNonIncreasing) {
                // Check the k elements after index i
                boolean isNonDecreasing = true;
                for (int j = i + 1; j < i + k; j++) {
                    if (nums[j] > nums[j + 1]) {
                        isNonDecreasing = false;
                        break;
                    }
                }

                if (isNonDecreasing) {
                    result.add(i);
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- Initialize an empty list `result` to store the good indices.
- Iterate through each index `i` in the range `[k, n - k - 1]`.
- For each `i`, we perform two separate checks:
  - **Check Before:** Create a loop to check the `k` elements before `i`. Iterate from `j = i - k` to `i - 2`. If `nums[j] < nums[j+1]`, the condition is not met, so we can stop checking for this `i` and continue to the next.
  - **Check After:** If the first check passed, create another loop to check the `k` elements after `i`. Iterate from `j = i + 1` to `i + k - 1`. If `nums[j] > nums[j+1]`, the condition is not met.
- If both checks pass, add `i` to the `result` list.
- After the main loop finishes, return the `result` list.

## Dynamic Programming with Precomputation
A more efficient approach is to avoid the redundant checks of the brute-force method by precomputing the necessary information. We can use dynamic programming to create two arrays: one that stores the length of the non-increasing subarray ending at each index, and another that stores the length of the non-decreasing subarray starting at each index.
**Time:** O(n), where n is the number of elements in `nums`. We perform three separate passes over the array: one to compute non-increasing lengths, one for non-decreasing lengths, and one to find the good indices. Each pass takes O(n) time. · **Space:** O(n) to store the two precomputed arrays (`non_increasing` and `non_decreasing`).
**Pros:** Highly efficient with a linear time complexity.; Guaranteed to pass all test cases within the time limit.
**Cons:** Requires O(n) extra space for the DP arrays, which might be a concern for very large `n` in a memory-constrained environment.
### Explanation
The core idea is to solve the problem in three linear passes:
1.  **First Pass (Left to Right):** Create an array `non_increasing` of size `n`. `non_increasing[i]` will store the length of the contiguous non-increasing subarray ending at index `i`. We can compute this by iterating from left to right. If `nums[i] <= nums[i-1]`, then `non_increasing[i] = non_increasing[i-1] + 1`; otherwise, the streak is broken, and `non_increasing[i] = 1`.
2.  **Second Pass (Right to Left):** Create an array `non_decreasing` of size `n`. `non_decreasing[i]` will store the length of the contiguous non-decreasing subarray starting at index `i`. We compute this by iterating from right to left. If `nums[i] <= nums[i+1]`, then `non_decreasing[i] = non_decreasing[i+1] + 1`; otherwise, `non_decreasing[i] = 1`.
3.  **Third Pass (Finding Good Indices):** Iterate through the potential good indices `i` from `k` to `n - k - 1`. An index `i` is good if:
    *   The `k` elements before it are non-increasing. This is true if the length of the non-increasing subarray ending at `i-1` is at least `k`. We check this with `non_increasing[i-1] >= k`.
    *   The `k` elements after it are non-decreasing. This is true if the length of the non-decreasing subarray starting at `i+1` is at least `k`. We check this with `non_decreasing[i+1] >= k`.
If both conditions are met, add `i` to the result list.

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

class Solution {
    public List<Integer> goodIndices(int[] nums, int k) {
        int n = nums.length;
        
        // non_increasing[i] stores the length of the non-increasing subarray ending at i
        int[] non_increasing = new int[n];
        non_increasing[0] = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] <= nums[i - 1]) {
                non_increasing[i] = non_increasing[i - 1] + 1;
            } else {
                non_increasing[i] = 1;
            }
        }

        // non_decreasing[i] stores the length of the non-decreasing subarray starting at i
        int[] non_decreasing = new int[n];
        non_decreasing[n - 1] = 1;
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] <= nums[i + 1]) {
                non_decreasing[i] = non_decreasing[i + 1] + 1;
            } else {
                non_decreasing[i] = 1;
            }
        }

        List<Integer> result = new ArrayList<>();
        // Iterate through possible good indices
        for (int i = k; i < n - k; i++) {
            // Check if the k elements before i are non-increasing
            boolean beforeOk = non_increasing[i - 1] >= k;
            
            // Check if the k elements after i are non-decreasing
            boolean afterOk = non_decreasing[i + 1] >= k;

            if (beforeOk && afterOk) {
                result.add(i);
            }
        }

        return result;
    }
}
```
### Algorithm
- Create an integer array `non_increasing` of size `n`.
- Iterate from `i = 1` to `n-1`. If `nums[i] <= nums[i-1]`, set `non_increasing[i] = non_increasing[i-1] + 1`. Otherwise, set `non_increasing[i] = 1`. Initialize `non_increasing[0] = 1`.
- Create an integer array `non_decreasing` of size `n`.
- Iterate from `i = n-2` down to `0`. If `nums[i] <= nums[i+1]`, set `non_decreasing[i] = non_decreasing[i+1] + 1`. Otherwise, set `non_decreasing[i] = 1`. Initialize `non_decreasing[n-1] = 1`.
- Initialize an empty list `result`.
- Iterate from `i = k` to `n - k - 1`.
- Check if `non_increasing[i-1] >= k` AND `non_decreasing[i+1] >= k`.
- If both conditions are true, add `i` to the `result` list.
- Return the `result` list.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> goodIndices(int[] nums, int k) {
    int n = nums.length;
    int[] decr = new int[n];
    int[] incr = new int[n];
    Arrays.fill(decr, 1);
    Arrays.fill(incr, 1);
    for (int i = 2; i < n - 1; ++i) {
      if (nums[i - 1] <= nums[i - 2]) {
        decr[i] = decr[i - 1] + 1;
      }
    }
    for (int i = n - 3; i >= 0; --i) {
      if (nums[i + 1] <= nums[i + 2]) {
        incr[i] = incr[i + 1] + 1;
      }
    }
    List<Integer> ans = new ArrayList<>();
    for (int i = k; i < n - k; ++i) {
      if (decr[i] >= k && incr[i] >= k) {
        ans.add(i);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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]

```