LeetCode 2420 - Find All Good Indices

The problem asks us to identify all good indices in an array nums based on a window size k. A good index i satisfies two conditions: the k elements immediately before it form a non-increasing sequence, and the k elements immediately after it form a non-decreasing sequence.

leetcodemediumarraydynamic-programmingprefix-sum

LeetCode Problem 2420

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Prefix Sum

Solution

Problem Understanding

The problem asks us to identify all good indices in an array nums based on a window size k. A good index i satisfies two conditions: the k elements immediately before it form a non-increasing sequence, and the k elements immediately after it form a non-decreasing sequence. The input is a 0-indexed array of integers, and k is a positive integer such that 1 <= k <= n/2, guaranteeing that both the prefix and suffix windows around the candidate index i exist. The output is a list of all such indices sorted in increasing order.

The constraints indicate that n can be as large as 10^5 and nums[i] can be up to 10^6. This rules out any brute-force solution that examines each window for every index in O(k) time, because the total work could be O(n*k) which is too slow.

Important edge cases include arrays with all equal elements, arrays that are strictly increasing or decreasing, k equal to 1, and arrays where no index satisfies the conditions. These are potential pitfalls for naive implementations.

Approaches

The brute-force approach checks each candidate index i individually. For each index, we extract the k elements before i and verify they are non-increasing, and extract the k elements after i and verify they are non-decreasing. This approach is correct but inefficient because each check costs O(k) and there are O(n) candidate indices, resulting in O(n*k) time complexity. For large n and k, this becomes infeasible.

The optimal approach relies on prefix information. We can precompute two arrays: nonInc and nonDec. nonInc[i] stores the length of the consecutive non-increasing sequence ending at index i, and nonDec[i] stores the length of the consecutive non-decreasing sequence starting at index i. Using these arrays, we can check in constant time whether an index i is good: if nonInc[i-1] >= k and nonDec[i+1] >= k, then index i is valid. This reduces the complexity to O(n).

Approach Time Complexity Space Complexity Notes
Brute Force O(n*k) O(1) Checks each candidate index individually by examining subarrays
Optimal O(n) O(n) Uses prefix and suffix arrays to check conditions in constant time per index

Algorithm Walkthrough

  1. Initialize two arrays nonInc and nonDec of size n with all values set to 1. nonInc[i] will store the length of the non-increasing sequence ending at i, and nonDec[i] the length of the non-decreasing sequence starting at i.
  2. Traverse the array from left to right to fill nonInc. For each index i > 0, if nums[i] <= nums[i-1], set nonInc[i] = nonInc[i-1] + 1. Otherwise, keep it 1.
  3. Traverse the array from right to left to fill nonDec. For each index i < n-1, if nums[i] <= nums[i+1], set nonDec[i] = nonDec[i+1] + 1. Otherwise, keep it 1.
  4. Iterate through all candidate indices i from k to n-k-1. For each index, check if nonInc[i-1] >= k and nonDec[i+1] >= k. If both conditions hold, add i to the result list.
  5. Return the result list sorted in increasing order.

Why it works: nonInc[i-1] captures exactly the length of the non-increasing segment ending just before index i, and nonDec[i+1] captures the non-decreasing segment starting just after index i. By comparing these lengths to k, we ensure that the prefix and suffix conditions for a good index are satisfied.

Python Solution

from typing import List

class Solution:
    def goodIndices(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        if n < 2*k + 1:
            return []

        nonInc = [1] * n
        nonDec = [1] * n

        for i in range(1, n):
            if nums[i] <= nums[i-1]:
                nonInc[i] = nonInc[i-1] + 1

        for i in range(n-2, -1, -1):
            if nums[i] <= nums[i+1]:
                nonDec[i] = nonDec[i+1] + 1

        result = []
        for i in range(k, n-k):
            if nonInc[i-1] >= k and nonDec[i+1] >= k:
                result.append(i)
        return result

The Python implementation first handles the edge case where the array is too short to have any good index. Then, it constructs the prefix and suffix arrays. Finally, it checks each candidate index using the precomputed lengths and appends the valid indices to the result.

Go Solution

func goodIndices(nums []int, k int) []int {
    n := len(nums)
    if n < 2*k+1 {
        return []int{}
    }

    nonInc := make([]int, n)
    nonDec := make([]int, n)
    for i := range nonInc {
        nonInc[i] = 1
        nonDec[i] = 1
    }

    for i := 1; i < n; i++ {
        if nums[i] <= nums[i-1] {
            nonInc[i] = nonInc[i-1] + 1
        }
    }

    for i := n-2; i >= 0; i-- {
        if nums[i] <= nums[i+1] {
            nonDec[i] = nonDec[i+1] + 1
        }
    }

    result := []int{}
    for i := k; i < n-k; i++ {
        if nonInc[i-1] >= k && nonDec[i+1] >= k {
            result = append(result, i)
        }
    }

    return result
}

In Go, slices are initialized with make and lengths set to 1. The logic mirrors the Python implementation exactly. We append good indices to a result slice which is then returned. There are no concerns about integer overflow here since the problem guarantees bounds within standard integer range.

Worked Examples

Example 1: nums = [2,1,1,1,3,4,1], k = 2

Step 1: Compute nonInc:

i=0: 1
i=1: 2 (1 <= 2)
i=2: 3 (1 <= 1)
i=3: 4 (1 <= 1)
i=4: 1 (3 <= 1? no) -> 1
i=5: 1 (4 <= 3? no) -> 1
i=6: 1
nonInc = [1,2,3,4,1,1,1]

Step 2: Compute nonDec:

i=6: 1
i=5: 1 (4 <= 1? no)
i=4: 2 (3 <= 4)
i=3: 3 (1 <= 3)
i=2: 4 (1 <= 1)
i=1: 5 (1 <= 1)
i=0: 1 (2 <= 1? no)
nonDec = [1,5,4,3,2,1,1]

Step 3: Check indices i=2..4:

i=2: nonInc[1]=2 >= k, nonDec[3]=3 >= k -> valid
i=3: nonInc[2]=3 >= k, nonDec[4]=2 >= k -> valid
i=4: nonInc[3]=4 >= k, nonDec[5]=1 < k -> invalid
Result = [2,3]

Example 2: nums = [2,1,1,2], k = 2

n=4, 2*k+1=5 > n -> automatically return []

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each of the two passes to compute nonInc and nonDec is O(n), and the final check is O(n)
Space O(n) Two auxiliary arrays of size n are used to store prefix and suffix lengths

The algorithm is linear in both time and space, which is optimal given the problem constraints.

Test Cases

# Provided examples
assert Solution().goodIndices([2,1,1,1,3,4,1], 2) == [2,3]  # normal case with valid indices
assert Solution().goodIndices([2,1,1,2], 2) == []           # array too short for valid indices

# Edge cases
assert Solution().goodIndices([