2420. Find All Good Indices

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 <= 10^5

• 1 <= nums[i] <= 10^6

• 1 <= k <= n / 2

Solution (Java)

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

        //For decr
        int n=nums.length;
        int []decrArr=new int[n];
        decrArr[0]=1;
        for(int i=1;i<nums.length;i++){
            if(nums[i]<=nums[i-1])decrArr[i]=1+decrArr[i-1];
            else decrArr[i]=1;
        }
        //For Incr
        int [] incArr=new int[n];
        incArr[nums.length-1]=1;
        for(int i=nums.length-2;i>=0;i--){
           if(nums[i]<=nums[i+1])incArr[i]=1+incArr[i+1]; 
           else incArr[i]=1;
        }
        //Logic
        List<Integer> res=new ArrayList<>();
        for(int i=1;i<n-1;i++){
            if(decrArr[i-1]>=k && incArr[i+1]>=k)
             res.add(i);
        } 
        return res;

    }
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).