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 inincreasing order.

Examples

Example 1

1
2
3
4
5
6

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

1
2
3

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^5
  • 1 <= nums[i] <= 10^6
  • 1 <= k <= n / 2

Solution

Method 1 – Prefix Arrays (Dynamic Programming)

Intuition

We want to efficiently check for each index if the k elements before it are non-increasing and the k elements after it are non-decreasing. We can precompute for each index how long the non-increasing and non-decreasing sequences are ending or starting at that index using prefix arrays.

Approach

  1. Create two arrays:
    • non_inc[i]: number of consecutive non-increasing elements ending at i (including i)
    • non_dec[i]: number of consecutive non-decreasing elements starting at i (including i)
  2. Fill non_inc from left to right:
    • If nums[i] <= nums[i-1], then non_inc[i] = non_inc[i-1] + 1, else 1
  3. Fill non_dec from right to left:
    • If nums[i] <= nums[i+1], then non_dec[i] = non_dec[i+1] + 1, else 1
  4. For each index i in range k to n-k-1:
    • If non_inc[i-1] >= k and non_dec[i+1] >= k, then i is a good index
  5. Return the list of good indices.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    vector<int> goodIndices(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> non_inc(n, 1), non_dec(n, 1), ans;
        for (int i = 1; i < n; ++i)
            if (nums[i] <= nums[i-1]) non_inc[i] = non_inc[i-1] + 1;
        for (int i = n-2; i >= 0; --i)
            if (nums[i] <= nums[i+1]) non_dec[i] = non_dec[i+1] + 1;
        for (int i = k; i < n-k; ++i)
            if (non_inc[i-1] >= k && non_dec[i+1] >= k) ans.push_back(i);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

func goodIndices(nums []int, k int) []int {
    n := len(nums)
    nonInc := make([]int, n)
    nonDec := make([]int, n)
    for i := range nonInc { nonInc[i] = 1; nonDec[i] = 1 }
    for i := 1; i < n; i++ {
        if nums[i] <= nums[i-1] {
            nonInc[i] = nonInc[i-1] + 1
        }
    }
    for i := n-2; i >= 0; i-- {
        if nums[i] <= nums[i+1] {
            nonDec[i] = nonDec[i+1] + 1
        }
    }
    ans := []int{}
    for i := k; i < n-k; i++ {
        if nonInc[i-1] >= k && nonDec[i+1] >= k {
            ans = append(ans, i)
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public List<Integer> goodIndices(int[] nums, int k) {
        int n = nums.length;
        int[] nonInc = new int[n], nonDec = new int[n];
        Arrays.fill(nonInc, 1); Arrays.fill(nonDec, 1);
        for (int i = 1; i < n; i++)
            if (nums[i] <= nums[i-1]) 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;
        List<Integer> ans = new ArrayList<>();
        for (int i = k; i < n-k; i++)
            if (nonInc[i-1] >= k && nonDec[i+1] >= k) ans.add(i);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun goodIndices(nums: IntArray, k: Int): List<Int> {
        val n = nums.size
        val nonInc = IntArray(n) { 1 }
        val nonDec = IntArray(n) { 1 }
        for (i in 1 until n)
            if (nums[i] <= nums[i-1]) nonInc[i] = nonInc[i-1] + 1
        for (i in n-2 downTo 0)
            if (nums[i] <= nums[i+1]) nonDec[i] = nonDec[i+1] + 1
        val ans = mutableListOf<Int>()
        for (i in k until n-k)
            if (nonInc[i-1] >= k && nonDec[i+1] >= k) ans.add(i)
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def goodIndices(self, nums: list[int], k: int) -> list[int]:
        n = len(nums)
        non_inc = [1] * n
        non_dec = [1] * n
        for i in range(1, n):
            if nums[i] <= nums[i-1]:
                non_inc[i] = non_inc[i-1] + 1
        for i in range(n-2, -1, -1):
            if nums[i] <= nums[i+1]:
                non_dec[i] = non_dec[i+1] + 1
        ans = []
        for i in range(k, n-k):
            if non_inc[i-1] >= k and non_dec[i+1] >= k:
                ans.append(i)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

impl Solution {
    pub fn good_indices(nums: Vec<i32>, k: i32) -> Vec<i32> {
        let n = nums.len();
        let k = k as usize;
        let mut non_inc = vec![1; n];
        let mut non_dec = vec![1; n];
        for i in 1..n {
            if nums[i] <= nums[i-1] {
                non_inc[i] = non_inc[i-1] + 1;
            }
        }
        for i in (0..n-1).rev() {
            if nums[i] <= nums[i+1] {
                non_dec[i] = non_dec[i+1] + 1;
            }
        }
        let mut ans = vec![];
        for i in k..n-k {
            if non_inc[i-1] >= k && non_dec[i+1] >= k {
                ans.push(i as i32);
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    goodIndices(nums: number[], k: number): number[] {
        const n = nums.length;
        const nonInc = Array(n).fill(1);
        const nonDec = Array(n).fill(1);
        for (let i = 1; i < n; i++)
            if (nums[i] <= nums[i-1]) 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;
        const ans: number[] = [];
        for (let i = k; i < n-k; i++)
            if (nonInc[i-1] >= k && nonDec[i+1] >= k) ans.push(i);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of nums. We scan the array a few times.
  • 🧺 Space complexity: O(n), for the prefix arrays.