Find All Good Indices - Video Solutions

Problem Overview: Given an integer array nums and an integer k, return all indices i where the previous k elements form a non-increasing sequence and the next k elements form a non-decreasing sequence. Only indices with at least k elements on both sides qualify.

Approach 1: Pre-calculated Arrays for Monotonic Subarrays (O(n) time, O(n) space)

The key observation: instead of rechecking monotonicity around every index, precompute it once. Build two arrays while iterating through the input. The first array stores how long the current non-increasing streak continues up to each index. The second stores how long the non-decreasing streak continues starting from each index when traversing from right to left. Once these arrays are filled, iterate through valid indices and check dec[i-1] >= k and inc[i+1] >= k. This avoids repeatedly scanning subarrays and reduces the solution to linear time. The technique resembles prefix-style preprocessing commonly used in array and dynamic programming problems where previous computations are reused.

Each pass over the array performs constant work, so the total runtime is O(n). Two auxiliary arrays of size n store the monotonic lengths, giving O(n) space complexity. This approach is straightforward, cache-friendly, and easy to reason about during interviews.

Approach 2: Sliding Window with Monotonic Checks (O(n) time, O(1) extra space)

Another option tracks monotonic violations while sliding windows of size k. Maintain counters representing how many positions break the non-increasing condition on the left window and how many break the non-decreasing condition on the right window. As the index moves forward, update the counters by removing the outgoing comparison and adding the new one. When both counters are zero, the current index satisfies the requirement. This technique avoids storing auxiliary arrays and processes the array in a single pass.

The sliding window pattern is common in array processing where constraints apply to fixed-size ranges. Each step updates only a few comparisons, so runtime stays O(n) with O(1) additional memory. Conceptually it resembles maintaining prefix-style validity information, similar to ideas used in prefix sum based preprocessing.

Recommended for interviews: The pre-calculated arrays approach is what most interviewers expect. It clearly shows you recognized the monotonic subarray structure and optimized repeated checks using preprocessing. Mentioning the brute-force idea first (checking each index with two loops) demonstrates problem understanding, but implementing the O(n) preprocessing solution shows strong algorithmic thinking.