Find All Good Indices

Problem 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.

Key Insights

• The problem involves checking conditions on subarrays of fixed lengths (k).
• A two-pass approach can be used: one to check for non-increasing order and another to check for non-decreasing order.
• Efficiently storing and checking the conditions allows us to determine the good indices without re-evaluating the same segments multiple times.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we will use two auxiliary arrays to keep track of the lengths of non-increasing and non-decreasing sequences. We iterate through the array to fill these arrays:

1. Create an array left where left[i] is the count of elements that are non-increasing ending at index i.
2. Create an array right where right[i] is the count of elements that are non-decreasing starting at index i.
3. Iterate through the nums array to fill the left array from left to right and the right array from right to left.
4. Finally, iterate through the valid indices (from k to n-k) and check if the conditions for being a good index are met using the left and right arrays.

Code Solutions