Watch 10 video solutions for Find All Good Indices, a medium level problem involving Array, Dynamic Programming, Prefix Sum. This walkthrough by Coding Decoded has 2,105 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
k elements that are just before the index i are in non-increasing order.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.length3 <= n <= 1051 <= nums[i] <= 1061 <= k <= n / 2