Problem Description

You have an array nums of integers (0-indexed) with size n, and a positive integer k.

An index i is considered good if it meets these conditions:

• The index must be in the range k <= i < n - k (meaning there are at least k elements before and after it)
• The k elements immediately before index i (from position i-k to i-1) must be in non-increasing order (each element is less than or equal to the previous one)
• The k elements immediately after index i (from position i+1 to i+k) must be in non-decreasing order (each element is greater than or equal to the previous one)

Your task is to find all good indices and return them as an array sorted in increasing order.

For example, if we have nums = [2,1,1,1,3,4,1] and k = 2:

• Index 2 would be good if the 2 elements before it [2,1] are non-increasing (✓) and the 2 elements after it [1,3] are non-decreasing (✓)
• We check each valid index in the range to determine if it's good

The solution uses dynamic programming to track:

• decr[i]: the length of the longest non-increasing sequence ending just before index i
• incr[i]: the length of the longest non-decreasing sequence starting just after index i

An index i is good when both decr[i] >= k and incr[i] >= k, meaning there are at least k elements in the required order on both sides.

Intuition

The key insight is that checking each index individually by examining k elements before and after would be inefficient, requiring O(n*k) time. Instead, we can precompute information about the ordering patterns throughout the array.

Think about what makes an index "good" - we need to know if there are at least k consecutive elements in non-increasing order before it, and at least k consecutive elements in non-decreasing order after it. Rather than checking this repeatedly for each index, we can build this information once for the entire array.

The crucial observation is that if we know the length of the longest non-increasing sequence ending at position i-1, we can determine if index i has at least k non-increasing elements before it. Similarly, if we know the length of the longest non-decreasing sequence starting at position i+1, we can determine if index i has at least k non-decreasing elements after it.

This leads us to use dynamic programming:

• For the non-increasing sequences before each index: we traverse left to right. If nums[i-1] <= nums[i-2], then the non-increasing sequence continues, so decr[i] = decr[i-1] + 1. Otherwise, it breaks and we reset to 1.
• For the non-decreasing sequences after each index: we traverse right to left. If nums[i+1] <= nums[i+2], then the non-decreasing sequence continues, so incr[i] = incr[i+1] + 1. Otherwise, it breaks and we reset to 1.

Once we've built these arrays in O(n) time, checking if an index is good becomes an O(1) operation - just verify if decr[i] >= k and incr[i] >= k. This reduces the overall complexity from O(n*k) to O(n).

Learn more about Dynamic Programming and Prefix Sum patterns.

Solution Approach

The solution uses dynamic programming with two auxiliary arrays to track the non-increasing and non-decreasing sequences.

Step 1: Initialize the arrays

• Create decr array of size n+1 initialized with 1s to track the length of non-increasing sequences ending just before each index
• Create incr array of size n+1 initialized with 1s to track the length of non-decreasing sequences starting just after each index

Step 2: Build the decr array (left to right)

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

• Start from index 2 (since we need to check nums[i-1] and nums[i-2])
• If nums[i-1] <= nums[i-2], the non-increasing pattern continues, so we extend the previous length by 1
• Otherwise, decr[i] remains 1 (the sequence breaks)
• decr[i] represents how many consecutive non-increasing elements exist just before index i

Step 3: Build the incr array (right to left)

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

• Start from index n-3 going backwards (since we need to check nums[i+1] and nums[i+2])
• If nums[i+1] <= nums[i+2], the non-decreasing pattern continues, so we extend the length from the right by 1
• Otherwise, incr[i] remains 1 (the sequence breaks)
• incr[i] represents how many consecutive non-decreasing elements exist just after index i

Step 4: Collect good indices

return [i for i in range(k, n - k) if decr[i] >= k and incr[i] >= k]

• Iterate through all valid indices in range [k, n-k)
• An index i is good if both:
  • decr[i] >= k: at least k elements before i are non-increasing
  • incr[i] >= k: at least k elements after i are non-decreasing
• The list comprehension automatically returns the indices in increasing order

Time Complexity: O(n) - we make three passes through the array Space Complexity: O(n) - for the two auxiliary arrays decr and incr

Example Walkthrough

Let's walk through the solution with nums = [2,1,1,1,3,4,1] and k = 2.

Step 1: Initialize arrays

• n = 7
• Valid index range: [2, 5) → indices 2, 3, 4
• decr = [1, 1, 1, 1, 1, 1, 1, 1] (size n+1)
• incr = [1, 1, 1, 1, 1, 1, 1, 1] (size n+1)

Step 2: Build decr array (left to right)

For i = 2:

• Check if nums[1] <= nums[0] → 1 <= 2 ✓
• decr[2] = decr[1] + 1 = 2

For i = 3:

• Check if nums[2] <= nums[1] → 1 <= 1 ✓
• decr[3] = decr[2] + 1 = 3

For i = 4:

• Check if nums[3] <= nums[2] → 1 <= 1 ✓
• decr[4] = decr[3] + 1 = 4

For i = 5:

• Check if nums[4] <= nums[3] → 3 <= 1 ✗
• decr[5] = 1 (sequence breaks)

Result: decr = [1, 1, 2, 3, 4, 1, 1, 1]

Step 3: Build incr array (right to left)

For i = 4:

• Check if nums[5] <= nums[6] → 4 <= 1 ✗
• incr[4] = 1 (sequence breaks)

For i = 3:

• Check if nums[4] <= nums[5] → 3 <= 4 ✓
• incr[3] = incr[4] + 1 = 2

For i = 2:

• Check if nums[3] <= nums[4] → 1 <= 3 ✓
• incr[2] = incr[3] + 1 = 3

For i = 1:

• Check if nums[2] <= nums[3] → 1 <= 1 ✓
• incr[1] = incr[2] + 1 = 4

For i = 0:

• Check if nums[1] <= nums[2] → 1 <= 1 ✓
• incr[0] = incr[1] + 1 = 5

Result: incr = [5, 4, 3, 2, 1, 1, 1, 1]

Step 4: Find good indices

Check each valid index in range [2, 5):

• Index 2: decr[2] = 2 >= 2 ✓ and incr[2] = 3 >= 2 ✓ → GOOD
• Index 3: decr[3] = 3 >= 2 ✓ and incr[3] = 2 >= 2 ✓ → GOOD
• Index 4: decr[4] = 4 >= 2 ✓ and incr[4] = 1 >= 2 ✗ → NOT GOOD

Final Answer: [2, 3]

The solution correctly identifies indices 2 and 3 as good:

• Index 2: Elements before [2,1] are non-increasing, elements after [1,3] are non-decreasing
• Index 3: Elements before [1,1] are non-increasing, elements after [3,4] are non-decreasing

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of three main parts:

• First loop: Iterates from index 2 to n-2, performing constant time operations at each step - O(n)
• Second loop: Iterates from index n-3 to 0, performing constant time operations at each step - O(n)
• List comprehension: Iterates through indices from k to n-k, performing constant time comparisons at each index - O(n)

Since these operations are sequential and not nested, the total time complexity is O(n) + O(n) + O(n) = O(n).

Space Complexity: O(n)

The algorithm uses:

• decr array of size n+1 - O(n)
• incr array of size n+1 - O(n)
• Output list in the worst case could contain up to n-2k elements - O(n)

The total space complexity is O(n) + O(n) + O(n) = O(n), where n is the length of the input array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Errors in Index Boundaries

Pitfall: One of the most common mistakes is incorrectly setting the loop boundaries when building the decreasing_length and increasing_length arrays. Developers often confuse:

• Whether to use n-1 or n-2 as the upper bound
• Whether to check nums[i-1] <= nums[i-2] or nums[i] <= nums[i-1]

Why it happens: The relationship between the index i and the elements being compared can be confusing. For decreasing_length[i], we're tracking the sequence that ends just before index i, not at index i.

Solution:

# Correct: For decreasing_length[i], we check elements BEFORE index i
for i in range(2, n - 1):  # Start at 2 because we need nums[i-2]
    if nums[i - 1] <= nums[i - 2]:  # Compare the two elements before i
        decreasing_length[i] = decreasing_length[i - 1] + 1

# Correct: For increasing_length[i], we check elements AFTER index i  
for i in range(n - 3, -1, -1):  # Stop at n-3 because we need nums[i+2]
    if nums[i + 1] <= nums[i + 2]:  # Compare the two elements after i
        increasing_length[i] = increasing_length[i + 1] + 1

2. Misunderstanding What the DP Arrays Represent

Pitfall: Confusing what decreasing_length[i] and increasing_length[i] actually represent. Some might think:

• decreasing_length[i] counts elements including index i
• increasing_length[i] counts elements including index i

Why it happens: The naming and indexing can be misleading without careful documentation.

Solution: Always remember:

• decreasing_length[i] = length of non-increasing sequence ending at position i-1 (excluding i)
• increasing_length[i] = length of non-decreasing sequence starting at position i+1 (excluding i)

Add clear comments:

# decreasing_length[i]: How many consecutive non-increasing elements 
#                       exist BEFORE index i (not including i)
# increasing_length[i]: How many consecutive non-decreasing elements 
#                       exist AFTER index i (not including i)

3. Incorrect Comparison Operators

Pitfall: Using the wrong comparison operator (< instead of <= or vice versa) when checking for non-increasing or non-decreasing sequences.

Why it happens: The problem requires:

• Non-increasing: each element ≤ previous (allows equal values)
• Non-decreasing: each element ≥ previous (allows equal values)

Solution: Use the correct operators:

# For non-increasing (allowing equal values): use <=
if nums[i - 1] <= nums[i - 2]:  # Correct

# For non-decreasing (allowing equal values): use <=
if nums[i + 1] <= nums[i + 2]:  # Correct

# Common mistake: using < instead of <=
if nums[i - 1] < nums[i - 2]:  # Wrong! This checks strictly decreasing

4. Edge Case Handling with Small Arrays

Pitfall: Not properly handling cases where n < 2k + 1, which means no valid indices can exist.

Why it happens: The range [k, n-k) can be empty if the array is too small.

Solution: Add an early return check:

def goodIndices(self, nums: List[int], k: int) -> List[int]:
    n = len(nums)
  
    # Early return if array is too small to have any good indices
    if n < 2 * k + 1:
        return []
  
    # Continue with the main algorithm...

5. Array Size Initialization Error

Pitfall: Creating arrays of size n instead of n+1, or not understanding why n+1 might be used.

Why it happens: Some implementations use size n+1 for easier indexing or to avoid boundary checks, but this can cause confusion.

Solution: Be consistent with array sizing and indexing:

# Option 1: Use size n (more memory efficient)
decreasing_length = [1] * n
increasing_length = [1] * n

# Option 2: Use size n+1 (might simplify some boundary cases)
decreasing_length = [1] * (n + 1)
increasing_length = [1] * (n + 1)
# But ensure you don't access out-of-bounds indices

The key is to be consistent throughout your implementation and understand how your chosen size affects the indexing logic.