Skip to content

2420. Find All Good Indices

Description

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

Solutions

Solution 1: Recursion

Thinking

At \(n\le 10^5\), checking \(k\) neighbors on each side per index can reach \(O(nk)\). The two sides are independent, so precompute the non-increasing run ending at \(i-1\) and the one starting at \(i+1\).

Fill \(\textit{decr}\) left to right and \(\textit{incr}\) right to left, then accept \(i\in[k,n-k)\) when both runs are at least \(k\). Both sides are non-increasing, matching the two \(\le\) comparisons in the code.

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.

 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]

 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
26
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;
    }
}

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

 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
26
func goodIndices(nums []int, k int) []int {
    n := len(nums)
    decr := make([]int, n)
    incr := make([]int, n)
    for i := range decr {
        decr[i] = 1
        incr[i] = 1
    }
    for i := 2; i < n; i++ {
        if nums[i-1] <= nums[i-2] {
            decr[i] = decr[i-1] + 1
        }
    }
    for i := n - 3; i >= 0; i-- {
        if nums[i+1] <= nums[i+2] {
            incr[i] = incr[i+1] + 1
        }
    }
    ans := []int{}
    for i := k; i < n-k; i++ {
        if decr[i] >= k && incr[i] >= k {
            ans = append(ans, i)
        }
    }
    return ans
}

Comments