2420. Find All Good Indices
Problem Description
In this problem, you are given an array nums
of integers and a positive integer k
. Your task is to find all the "good" indices in this array. An index i
is considered "good" if it satisfies two conditions based on the elements around it:
- The
k
elements immediately before indexi
are in non-increasing order. This means each element is less than or equal to the element before it. - The
k
elements immediately after indexi
are in non-decreasing order. This means each element is greater than or equal to the element after it.
The problem constraints are such that the "good" indices have to be in the range k <= i < n - k
, which means you do not need to consider the first k
indices and the last k
indices of the array. The task is to return all "good" indices in increasing order.
For example, given nums = [2,1,1,1,3,4,1]
and k = 2
, index 3
is "good" because the two elements before it [2,1]
are in non-increasing order and the two elements after it [3,4]
are in non-decreasing order.
Intuition
The key to solving this problem lies in efficiently checking the two conditions for "good" indices without repeatedly iterating over k
elements for each potential "good" index. To do this, we can preprocess the array to create two additional arrays:
- An array
decr
to keep track of the length of non-increasing sequences ending at each index.decr[i]
gives the length of the non-increasing sequence before indexi
. - An array
incr
to keep record of the length of non-decreasing sequences starting at each index.incr[i]
gives the length of the non-decreasing sequence after indexi
.
By precomputing these values, we can quickly check whether an index is "good" by simply verifying if decr[i] >= k
and incr[i] >= k
. The preprocessing is efficient because each element only needs to be compared with its immediate predecessor or successor to update the decr
and incr
arrays respectively.
The process is as follows:
- Initialize the
decr
andincr
arrays to be of lengthn + 1
with all values set to1
. This accounts for the fact that each index is by default part of a non-increasing or non-decreasing sequence of length 1 (itself). - Populate the
decr
array starting from the second element up to the second to last element by comparing each element with the one before it. - Populate the
incr
array starting from the second to last element back to the second element by comparing each element with the one after it. - Iterate over the range
k
ton - k
to collect all "good" indices where bothdecr[i] >= k
andincr[i] >= k
hold true.
The provided solution code correctly implements this approach, thus making the process of finding "good" indices efficient.
Learn more about Dynamic Programming and Prefix Sum patterns.
Solution Approach
The solution uses a straightforward approach with dynamic programming techniques to keep track of the lengths of non-increasing and non-decreasing subsequences around each index. Here's a step-by-step breakdown of how the algorithm and data structures are used:
-
Initialization of Arrays: The
decr
andincr
arrays are initialized to be of sizen + 1
, with all elements set to1
. These arrays are used to store the lengths of non-increasing and non-decreasing subsequences, respectively. This initial setup caters to the fact that solitary elements can be considered as subsequences of length one. -
Dynamic Programming - Filling
decr
Array: Thedecr
array is populated in a forward pass starting from index2
up ton - 1
. For every indexi
, if the current elementnums[i - 1]
is less than or equal to its previous elementnums[i - 2]
, thendecr[i]
is updated to bedecr[i - 1] + 1
, indicating that the non-increasing sequence continues.- The check
nums[i - 1] <= nums[i - 2]
confirms that the sequence is non-increasing at the point beforei
. - The
decr[i]
array captures the length of non-increasing order, which can be utilized later to check if an indexi
hask
non-increasing elements before it.
- The check
-
Dynamic Programming - Filling
incr
Array: Similarly, theincr
array is filled in a backward pass from indexn - 3
to0
. For every indexi
, if the current elementnums[i + 1]
is less than or equal to the next elementnums[i + 2]
, thenincr[i]
is updated to beincr[i + 1] + 1
.- The condition
nums[i + 1] <= nums[i + 2]
ensures that the sequence afteri
is non-decreasing. - By using
incr[i]
, we can efficiently determine if there arek
non-decreasing elements after indexi
.
- The condition
-
Find Good Indices: After populating
decr
andincr
, the solution then iterates through the valid range of indices (k
ton - k
- 1) and checks whether the conditions for "good" indices are met for each index. An indexi
is "good" ifdecr[i] >= k
andincr[i] >= k
. -
Result Collection: The indices that satisfy the good condition are added to the resultant list. This is done through a list comprehension that iterates over the valid range and includes the value
i
if it passes the check.
This algorithm effectively reduces the time complexity from what could be a brute-force check using nested loops (which would be O(nk)) down to O(n) because each element in nums
is processed a constant number of times.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a smaller example to illustrate the solution approach. Assume we have an array nums = [5, 4, 3, 7, 8, 5, 4, 2, 1, 6]
and k = 3
. We want to find all "good" indices.
Step 1: Initialization of Arrays
We initialize decr
and incr
arrays of length n + 1
(where n
is the length of nums
, which is 10) and set all values to 1
.
Initial decr
: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Initial incr
: [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
Step 2: Dynamic Programming - Filling decr
Array
We populate decr
array from the second element to the second to last:
decr[2]
remains1
(since5 <= 5
is false).decr[3] = decr[2] + 1 = 2
(since4 <= 5
is true).decr[4] = decr[3] + 1 = 3
(since3 <= 4
is true).decr[5]
resets to1
(since7 <= 3
is false).- ... Continue this for the rest of the array.
Updated decr
: [1, 1, 1, 2, 3, 1, 1, 2, 3, 1, 1]
Step 3: Dynamic Programming - Filling incr
Array
We populate incr
array in a backward pass:
incr[8] = incr[9] + 1 = 2
(since2 <= 1
is false).incr[7] = incr[8] + 1 = 3
(since4 <= 2
is false).incr[6]
resets to1
(since5 <= 4
is false).- ... Continue this pass for the rest of the array.
Updated incr
: [1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 1]
Step 4: Find Good Indices
We then loop through the range k to n - k and check if both decr[i] >= k
and incr[i] >= k
:
i = 3
does not satisfydecr[3] >= 3
.i = 4
satisfies bothdecr[4] >= 3
andincr[4] >= 3
.- ... Continue this for the range.
Step 5: Result Collection
We collect all "good" indices. For our example, the only "good" index we find is 4
. Thus, the output is [4]
.
Applying this solution to larger arrays is efficient because it avoids repeated calculations for each index, instead utilizing the precomputed decr
and incr
arrays for quick lookups.
Solution Implementation
1from typing import List
2
3class Solution:
4 def good_indices(self, nums: List[int], k: int) -> List[int]:
5 # Initialize the length of the 'nums' list
6 n = len(nums)
7
8 # Initialize two lists to track the non-increasing sequence lengths
9 # to the left and non-decreasing sequence lengths to the right of every index
10 non_increasing_lengths = [1] * (n + 1)
11 non_decreasing_lengths = [1] * (n + 1)
12
13 # Build the non-increasing sequence length array
14 for i in range(2, n - 1):
15 # If current and previous elements form a non-increasing sequence,
16 # increment the length at the current index
17 if nums[i - 1] <= nums[i - 2]:
18 non_increasing_lengths[i] = non_increasing_lengths[i - 1] + 1
19
20 # Build the non-decreasing sequence length array in reverse order
21 for i in range(n - 3, -1, -1):
22 # If the next element and the one after it form a non-decreasing sequence,
23 # increment the length at the current index
24 if nums[i + 1] <= nums[i + 2]:
25 non_decreasing_lengths[i] = non_decreasing_lengths[i + 1] + 1
26
27 # Find all 'good' indices, where both the non-increasing sequence on the left
28 # and the non-decreasing sequence on the right are at least 'k' elements long
29 good_indices = [i for i in range(k, n - k) if non_increasing_lengths[i] >= k and non_decreasing_lengths[i] >= k]
30
31 return good_indices
32
1class Solution {
2 public List<Integer> goodIndices(int[] nums, int k) {
3 // Initialize the length of the array
4 int n = nums.length;
5 // Create array to store the lengths of decreasing sequences
6 int[] decreasingLengths = new int[n];
7 // Create array to store the lengths of increasing sequences
8 int[] increasingLengths = new int[n];
9
10 // Initially set lengths of sequences to 1 for all elements
11 Arrays.fill(decreasingLengths, 1);
12 Arrays.fill(increasingLengths, 1);
13
14 // Calculate lengths of non-increasing sequences to the left of every index
15 for (int i = 1; i < n - 1; ++i) {
16 if (nums[i] <= nums[i - 1]) {
17 decreasingLengths[i + 1] = decreasingLengths[i] + 1;
18 }
19 }
20
21 // Calculate lengths of non-decreasing sequences to the right of every index
22 for (int i = n - 2; i > 0; --i) {
23 if (nums[i] <= nums[i + 1]) {
24 increasingLengths[i - 1] = increasingLengths[i] + 1;
25 }
26 }
27
28 // Initialize list to store all the good indices
29 List<Integer> goodIndices = new ArrayList<>();
30
31 // Traverse the array and add indices to the list that are good indices
32 for (int i = k; i < n - k; ++i) {
33 // A index is good if there are at least k non-increasing elements before it
34 // and at least k non-decreasing elements after it
35 if (decreasingLengths[i] >= k && increasingLengths[i] >= k) {
36 goodIndices.add(i);
37 }
38 }
39
40 // Return the list containing all the good indices found
41 return goodIndices;
42 }
43}
44
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 // Function to find all good indices based on the given conditions
7 vector<int> goodIndices(vector<int>& nums, int k) {
8 int n = nums.size(); // Total number of elements in nums
9 // Arrays to keep the lengths of non-increasing and non-decreasing subsequences
10 vector<int> nonIncrLens(n, 1);
11 vector<int> nonDecrLens(n, 1);
12
13 // Calculate lengths of non-increasing subsequences from the start
14 for (int i = 1; i < n; ++i) {
15 if (nums[i] <= nums[i - 1]) {
16 nonIncrLens[i] = nonIncrLens[i - 1] + 1;
17 }
18 }
19
20 // Calculate lengths of non-decreasing subsequences from the end
21 for (int i = n - 2; i >= 0; --i) {
22 if (nums[i] <= nums[i + 1]) {
23 nonDecrLens[i] = nonDecrLens[i + 1] + 1;
24 }
25 }
26
27 // Vector to store the good indices
28 vector<int> goodIndices;
29
30 // Iterate through the array to find all the good indices
31 for (int i = k; i < n - k; ++i) {
32 // Check if the current index i is a good index
33 if (nonIncrLens[i - 1] >= k && nonDecrLens[i + 1] >= k) {
34 goodIndices.push_back(i);
35 }
36 }
37
38 // Return the list of all good indices
39 return goodIndices;
40 }
41};
42
1// TypeScript doesn't have a direct equivalent to the C++ <vector> library, so we use arrays instead.
2
3// Function to find all good indices based on the given conditions
4function goodIndices(nums: number[], k: number): number[] {
5 const n: number = nums.length; // Total number of elements in nums
6 // Arrays to keep the lengths of non-increasing and non-decreasing subsequences
7 let nonIncrLens: number[] = new Array(n).fill(1);
8 let nonDecrLens: number[] = new Array(n).fill(1);
9
10 // Calculate lengths of non-increasing subsequences from the start
11 for (let i = 1; i < n; ++i) {
12 if (nums[i] <= nums[i - 1]) {
13 nonIncrLens[i] = nonIncrLens[i - 1] + 1;
14 }
15 }
16
17 // Calculate lengths of non-decreasing subsequences from the end
18 for (let i = n - 2; i >= 0; --i) {
19 if (nums[i] <= nums[i + 1]) {
20 nonDecrLens[i] = nonDecrLens[i + 1] + 1;
21 }
22 }
23
24 // Array to store the good indices
25 let goodIndicesList: number[] = [];
26
27 // Iterate through the array to find all the good indices
28 for (let i = k; i < n - k; ++i) {
29 // Check if the current index i is a good index
30 if (nonIncrLens[i - 1] >= k && nonDecrLens[i + 1] >= k) {
31 goodIndicesList.push(i);
32 }
33 }
34
35 // Return the list of all good indices
36 return goodIndicesList;
37}
38
Time and Space Complexity
The given Python code consists of two main parts ā first, creating non-increasing (decr
) and non-decreasing (incr
) prefix arrays, and second, iterating through the range [k, n - k)
to check and collect good indices based on the condition given in the problem.
Time Complexity
-
Building the non-increasing prefix array
decr
:- We iterate once from the index
2
ton - 1
(one-based indexing). In each iteration, we check a condition and possibly increment a value at the current index based on the previous index. - Each operation is
O(1)
, and since we do thisn - 2
times, this part has a time complexity ofO(n)
.
- We iterate once from the index
-
Building the non-decreasing prefix array
incr
:- Similarly, we iterate backward from
n - 3
to0
, doing anO(1)
operation each time. - This back traversal is done
n - 3
times, also yielding a time complexity ofO(n)
.
- Similarly, we iterate backward from
-
Finding good indices:
- We iterate through the range
[k, n - k)
and check two conditions for each indexi
, which again takesO(1)
per index. - There are
n - 2k
such indices, leading this part to have a time complexity ofO(n - 2k)
. However, sincek
is at mostn
, this simplifies toO(n)
.
- We iterate through the range
Considering all three parts, the overall time complexity combines to:
O(n) + O(n) + O(n) = O(3n)
which simplifies toO(n)
.
Space Complexity
-
Space used by
decr
andincr
arrays:- Both arrays have a size of
n + 1
, so the space taken by each isO(n)
. - Combined, they utilize
2 * (n + 1)
memory space, which simplifies toO(2n)
or justO(n)
.
- Both arrays have a size of
-
Space used for the output list:
- In the worst-case scenario, every index from
k
ton - k
may be a good index, so this list can take up ton - 2k
spaces. - The worst case for this list is also when
k
is very small compared ton
, which would make its space complexity approachO(n)
.
- In the worst-case scenario, every index from
Therefore, combining the space complexities from the arrays and the final output list, we get:
O(n) + O(n) = O(2n)
which simplifies toO(n)
.
In conclusion, the time complexity of the code is O(n)
and the space complexity is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!