Scale Engineer

Find All Good Indices

Med
#2204Time: 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: 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.2 companies
Patterns
Dynamic ProgrammingPrefix Sum
Data structures
Array
Companies
ByteDanceGoldman Sachs

Prompt

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 <= 105
  • 1 <= nums[i] <= 106
  • 1 <= k <= n / 2

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

  1. 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.
  2. 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

Time

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

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.

Trade-offs

Pros

  • Simple to understand and implement.

Cons

  • Inefficient due to redundant computations of checking subarray properties.

  • Likely to time out on larger test cases.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem