Find All Good Indices

MEDIUM

Description

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.
The k elements that are just after the index i are in non-decreasing order.

Return an array of all good indices sorted in increasing order.

Example 1:

Input: nums = [2,1,1,1,3,4,1], k = 2
Output: [2,3]
Explanation: There are two good indices in the array:
- Index 2. The subarray [2,1] is in non-increasing order, and the subarray [1,3] is in non-decreasing order.
- Index 3. The subarray [1,1] is in non-increasing order, and the subarray [3,4] is in non-decreasing order.
Note that the index 4 is not good because [4,1] is not non-decreasing.

Example 2:

Input: nums = [2,1,1,2], k = 2
Output: []
Explanation: There are no good indices in this array.

Constraints:

n == nums.length
3 <= n <= 10⁵
1 <= nums[i] <= 10⁶
1 <= k <= n / 2

Approaches

Checkout 2 different approaches to solve Find All Good Indices. Click on different approaches to view the approach and algorithm in detail.

Brute Force Iteration

The most straightforward approach is to iterate through every possible index i that could be a 'good' index and, for each one, verify if it meets the two specified conditions directly by checking the subarrays before and after it.

Algorithm

Initialize an empty list result to store the good indices.
Iterate through each index i in the range [k, n - k - 1].
For each i, we perform two separate checks:
- Check Before: Create a loop to check the k elements before i. Iterate from j = i - k to i - 2. If nums[j] < nums[j+1], the condition is not met, so we can stop checking for this i and continue to the next.
- Check After: If the first check passed, create another loop to check the k elements after i. Iterate from j = i + 1 to i + k - 1. If nums[j] > nums[j+1], the condition is not met.
If both checks pass, add i to the result list.
After the main loop finishes, return the result list.

We can loop through all indices i from k to n - k - 1. For each i, we perform two separate checks:

Check Before: We check if the subarray nums[i-k...i-1] is non-increasing. This is done by iterating from j = i-k to i-2 and ensuring nums[j] >= nums[j+1] for all j.
Check After: If the first condition holds, we check if the subarray nums[i+1...i+k] is non-decreasing. This is done by iterating from j = i+1 to i+k-1 and ensuring nums[j] <= nums[j+1] for all j.

If both conditions are satisfied, we add the index i to our result list. Since we iterate through i in increasing order, the final list will also be sorted.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> goodIndices(int[] nums, int k) {
        int n = nums.length;
        List<Integer> result = new ArrayList<>();

        // Iterate through all possible good indices
        for (int i = k; i < n - k; i++) {
            // Check the k elements before index i
            boolean isNonIncreasing = true;
            for (int j = i - k; j < i - 1; j++) {
                if (nums[j] < nums[j + 1]) {
                    isNonIncreasing = false;
                    break;
                }
            }

            if (isNonIncreasing) {
                // Check the k elements after index i
                boolean isNonDecreasing = true;
                for (int j = i + 1; j < i + k; j++) {
                    if (nums[j] > nums[j + 1]) {
                        isNonDecreasing = false;
                        break;
                    }
                }

                if (isNonDecreasing) {
                    result.add(i);
                }
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n * k), where n is the number of elements in `nums`. For each of the `n - 2k` potential indices, we perform two separate checks, each taking O(k) time. This can lead to a Time Limit Exceeded error for large inputs.Space Complexity: O(1) if we don't count the output list. The space required for the result list can be up to O(n) in the worst case.

Pros and Cons

Pros:

Simple to understand and implement.

Cons:

Inefficient due to redundant computations of checking subarray properties.
Likely to time out on larger test cases.

Code Solutions

Checking out 3 solutions in different languages for Find All Good Indices. Click on different languages to view the code.

class Solution {
public
  List<Integer> goodIndices(int[] nums, int k) {
    int n = nums.length;
    int[] decr = new int[n];
    int[] incr = new int[n];
    Arrays.fill(decr, 1);
    Arrays.fill(incr, 1);
    for (int i = 2; i < n - 1; ++i) {
      if (nums[i - 1] <= nums[i - 2]) {
        decr[i] = decr[i - 1] + 1;
      }
    }
    for (int i = n - 3; i >= 0; --i) {
      if (nums[i + 1] <= nums[i + 2]) {
        incr[i] = incr[i + 1] + 1;
      }
    }
    List<Integer> ans = new ArrayList<>();
    for (int i = k; i < n - k; ++i) {
      if (decr[i] >= k && incr[i] >= k) {
        ans.add(i);
      }
    }
    return ans;
  }
}

Video Solution

Watch the video walkthrough for Find All Good Indices

Patterns:

Dynamic ProgrammingPrefix Sum

Data Structures:

Array

Companies:

ByteDance |Goldman Sachs |