Find All Good Indices — LeetCode 2420 Python Solution

The problem

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.

Example

Input

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

Output

[2,3]

Explanation

There are two good indices in the array:

Python solution

class Solution:
    def goodIndices(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        decr = [1] * (n + 1)
        incr = [1] * (n + 1)
        for i in range(2, n - 1):
            if nums[i - 1] <= nums[i - 2]:
                decr[i] = decr[i - 1] + 1
        for i in range(n - 3, -1, -1):
            if nums[i + 1] <= nums[i + 2]:
                incr[i] = incr[i + 1] + 1
        return [i for i in range(k, n - k) if decr[i] >= k and incr[i] >= k]

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2420. Find All Good Indices is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems