Find All Good Indices

Find All Good Indices

What is this problem about?

In the Find All Good Indices interview question, you are given an array nums and an integer k. An index i is called "good" if:

1. There are at least $k$ elements before it ($i \ge k$).
2. There are at least $k$ elements after it ($i < n-k$).
3. The $k$ elements immediately before i are in non-increasing order.
4. The $k$ elements immediately after i are in non-decreasing order. You need to return a sorted list of all such good indices.

Why is this asked in interviews?

Goldman Sachs and ByteDance use this to test your ability to perform efficient preprocessing. Checking the $k$-neighborhood for every index from scratch would take $O(N imes K)$, which is too slow. It evaluation your proficiency with the Dynamic Programming interview pattern or Prefix Sum interview pattern to precalculate the lengths of monotonic sequences at every position.

Algorithmic pattern used

This problem uses Precomputation with two arrays:

1. before[i]: The length of the non-increasing sequence ending at $i-1$.
2. after[i]: The length of the non-decreasing sequence starting at $i+1$. You build these in linear time. For before, if nums[i-1] <= nums[i-2], then before[i] = before[i-1] + 1. Similarly for after. Once you have these arrays, an index $i$ is "good" if both before[i] >= k and after[i] >= k.

Example explanation

nums = [2, 1, 1, 1, 3, 4, 1], $k = 2$.

1. Precompute before:
   • At index 2: [2, 1] is non-increasing. Count = 2.
   • At index 3: [1, 1] is non-increasing. Count = 2.
2. Precompute after:
   • At index 2: [1, 1] is non-decreasing. Count = 2.
   • At index 3: [1, 3, 4] is non-decreasing... but only looking at the $k$ elements starting at index 4.
3. Check index 2: before[2]=2, after[2]=3. Since both $\ge 2$, index 2 is good.
4. Check index 3: before[3]=2, after[3]=2. Since both $\ge 2$, index 3 is good.

Common mistakes candidates make

• Inefficient checking: Re-scanning the $k$ elements for every index, leading to $O(N imes K)$.
• Confusion between non-increasing and non-decreasing: Swapping the logic for the left and right sides.
• Handling equal elements: Not realizing that "non-increasing" means $a \ge b$, and "non-decreasing" means $a \le b$ (equality is allowed).

Interview preparation tip

When a problem requires checking properties of ranges centered at every index, always think: "Can I precalculate this property from the left and from the right separately?" This "Two-Pass" preprocessing is a vital Array interview pattern.