Find All Good Indices

Medium
1161.

Find All Good Indices

Find All Good Indices is a medium coding problem on arrays, dynamic programming and prefix sum, asked in Amazon and Google interviews.

Index i of the 0-indexed array nums (length n) is good when k <= i < n - k and:

  • the k elements just before i (nums[i-k..i-1]) are in non-increasing order, and
  • the k elements just after i (nums[i+1..i+k]) are in non-decreasing order.

The value at i itself is not compared with anything. Return all good indices in ascending order.

Example 1

Input
nums = [5,4,4,3,6,2,2,7,8], k = 2
Output
[2,4,6]
Explanation
Index 2: `[5,4]` falls and `[3,6]` rises. Index 4: `[4,3]` and `[2,2]`. Index 6: `[6,2]` and `[7,8]`. Index 3 fails because `[6,2]` after it falls.

Example 2

Input
nums = [1,2,3,4,5], k = 2
Output
[]
Explanation
Only index 2 is in range, and `[1,2]` before it is increasing.

Constraints

  • n == nums.length
  • 3 <= n <= 10^5
  • 1 <= nums[i] <= 10^6
  • 1 <= k <= n / 2
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var goodIndices = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find All Good Indices — Solution in Python, Java & C++

Find All Good Indices solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find All Good Indices is a medium coding problem on arrays, dynamic programming and prefix sum, asked in Amazon and Google interviews.

Problem statement

Index i of the 0-indexed array nums (length n) is good when k <= i < n - k and:

  • the k elements just before i (nums[i-k..i-1]) are in non-increasing order, and
  • the k elements just after i (nums[i+1..i+k]) are in non-decreasing order.

The value at i itself is not compared with anything. Return all good indices in ascending order.

Example 1

Input: nums = [5,4,4,3,6,2,2,7,8], k = 2
Output: [2,4,6]
Explanation: Index 2: `[5,4]` falls and `[3,6]` rises. Index 4: `[4,3]` and `[2,2]`. Index 6: `[6,2]` and `[7,8]`. Index 3 fails because `[6,2]` after it falls.

Example 2

Input: nums = [1,2,3,4,5], k = 2
Output: []
Explanation: Only index 2 is in range, and `[1,2]` before it is increasing.

Constraints

  • n == nums.length
  • 3 <= n <= 10^5
  • 1 <= nums[i] <= 10^6
  • 1 <= k <= n / 2

Hints for Find All Good Indices

  1. Hint 1

    Checking 2k neighbours for every index costs O(n·k).

  2. Hint 2

    Precompute, for every position, how long the non-increasing run ending there is.

  3. Hint 3

    Likewise the non-decreasing run starting at each position (scan from the right). Index i is good when the run ending at i - 1 and the run starting at i + 1 are both at least k long.

How to solve Find All Good Indices

"The k elements before i are non-increasing" is the same as "the non-increasing run ending at i - 1 has length at least k". Run lengths for every position take one pass each, after which every index is checked in O(1).

Approach

  1. dec[j] = length of the longest non-increasing run ending at j: dec[j] = dec[j-1] + 1 if nums[j] <= nums[j-1], else 1.
  2. inc[j] = length of the longest non-decreasing run starting at j: scan from the right, inc[j] = inc[j+1] + 1 if nums[j] <= nums[j+1], else 1.
  3. For i from k to n - k - 1, keep i when dec[i-1] >= k and inc[i+1] >= k.
  4. The indices come out in ascending order.

Why it works

A window of k elements ending at i - 1 is non-increasing exactly when every adjacent pair inside it is, which is exactly when the maximal non-increasing run ending at i - 1 covers it — i.e. has length at least k. The same holds for the window after i with the non-decreasing run starting at i + 1.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Equal neighbours are allowed on both sides (non-increasing / non-decreasing, not strict).
  • nums[i] itself is not part of either window.
  • The index range is k <= i < n - k; indices outside it are never good.

Reference solution

Python

from typing import List

def goodIndices(nums: List[int], k: int) -> List[int]:
    n = len(nums)
    dec = [1] * n
    for i in range(1, n):
        if nums[i] <= nums[i - 1]:
            dec[i] = dec[i - 1] + 1
    inc = [1] * n
    for i in range(n - 2, -1, -1):
        if nums[i] <= nums[i + 1]:
            inc[i] = inc[i + 1] + 1
    return [i for i in range(k, n - k) if dec[i - 1] >= k and inc[i + 1] >= k]

Java

public static int[] goodIndices(int[] nums, int k) {
    int n = nums.length;
    int[] dec = new int[n], inc = new int[n];
    Arrays.fill(dec, 1);
    Arrays.fill(inc, 1);
    for (int i = 1; i < n; i++) if (nums[i] <= nums[i - 1]) dec[i] = dec[i - 1] + 1;
    for (int i = n - 2; i >= 0; i--) if (nums[i] <= nums[i + 1]) inc[i] = inc[i + 1] + 1;
    List<Integer> res = new ArrayList<>();
    for (int i = k; i < n - k; i++) if (dec[i - 1] >= k && inc[i + 1] >= k) res.add(i);
    int[] out = new int[res.size()];
    for (int i = 0; i < out.length; i++) out[i] = res.get(i);
    return out;
}

C++

vector<int> goodIndices(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> dec(n, 1), inc(n, 1);
    for (int i = 1; i < n; i++) if (nums[i] <= nums[i - 1]) dec[i] = dec[i - 1] + 1;
    for (int i = n - 2; i >= 0; i--) if (nums[i] <= nums[i + 1]) inc[i] = inc[i + 1] + 1;
    vector<int> res;
    for (int i = k; i < n - k; i++) if (dec[i - 1] >= k && inc[i + 1] >= k) res.push_back(i);
    return res;
}

JavaScript

var goodIndices = function(nums, k) {
    var n = nums.length;
    var dec = new Array(n).fill(1), inc = new Array(n).fill(1);
    for (var i = 1; i < n; i++) if (nums[i] <= nums[i - 1]) dec[i] = dec[i - 1] + 1;
    for (var j = n - 2; j >= 0; j--) if (nums[j] <= nums[j + 1]) inc[j] = inc[j + 1] + 1;
    var res = [];
    for (var p = k; p < n - k; p++) if (dec[p - 1] >= k && inc[p + 1] >= k) res.push(p);
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming