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.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Index i of the 0-indexed array nums (length n) is good when k <= i < n - k and:
- the
kelements just beforei(nums[i-k..i-1]) are in non-increasing order, and - the
kelements just afteri(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.length3 <= n <= 10^51 <= nums[i] <= 10^61 <= k <= n / 2
Hints for Find All Good Indices
Hint 1
Checking
2kneighbours for every index costs O(n·k).Hint 2
Precompute, for every position, how long the non-increasing run ending there is.
Hint 3
Likewise the non-decreasing run starting at each position (scan from the right). Index
iis good when the run ending ati - 1and the run starting ati + 1are both at leastklong.
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
dec[j]= length of the longest non-increasing run ending atj:dec[j] = dec[j-1] + 1ifnums[j] <= nums[j-1], else 1.inc[j]= length of the longest non-decreasing run starting atj: scan from the right,inc[j] = inc[j+1] + 1ifnums[j] <= nums[j+1], else 1.- For
ifromkton - k - 1, keepiwhendec[i-1] >= kandinc[i+1] >= k. - 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