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:

  1. The k elements immediately before index i are in non-increasing order. This means each element is less than or equal to the element before it.
  2. The k elements immediately after index i 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:

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

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 and incr arrays to be of length n + 1 with all values set to 1. 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 to n - k to collect all "good" indices where both decr[i] >= k and incr[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:

  1. Initialization of Arrays: The decr and incr arrays are initialized to be of size n + 1, with all elements set to 1. 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.

  2. Dynamic Programming - Filling decr Array: The decr array is populated in a forward pass starting from index 2 up to n - 1. For every index i, if the current element nums[i - 1] is less than or equal to its previous element nums[i - 2], then decr[i] is updated to be decr[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 before i.
    • The decr[i] array captures the length of non-increasing order, which can be utilized later to check if an index i has k non-increasing elements before it.
  3. Dynamic Programming - Filling incr Array: Similarly, the incr array is filled in a backward pass from index n - 3 to 0. For every index i, if the current element nums[i + 1] is less than or equal to the next element nums[i + 2], then incr[i] is updated to be incr[i + 1] + 1.

    • The condition nums[i + 1] <= nums[i + 2] ensures that the sequence after i is non-decreasing.
    • By using incr[i], we can efficiently determine if there are k non-decreasing elements after index i.
  4. Find Good Indices: After populating decr and incr, the solution then iterates through the valid range of indices (k to n - k - 1) and checks whether the conditions for "good" indices are met for each index. An index i is "good" if decr[i] >= k and incr[i] >= k.

  5. 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 Evaluator

Example 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] remains 1 (since 5 <= 5 is false).
  • decr[3] = decr[2] + 1 = 2 (since 4 <= 5 is true).
  • decr[4] = decr[3] + 1 = 3 (since 3 <= 4 is true).
  • decr[5] resets to 1 (since 7 <= 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 (since 2 <= 1 is false).
  • incr[7] = incr[8] + 1 = 3 (since 4 <= 2 is false).
  • incr[6] resets to 1 (since 5 <= 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 satisfy decr[3] >= 3.
  • i = 4 satisfies both decr[4] >= 3 and incr[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

  1. Building the non-increasing prefix array decr:

    • We iterate once from the index 2 to n - 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 this n - 2 times, this part has a time complexity of O(n).
  2. Building the non-decreasing prefix array incr:

    • Similarly, we iterate backward from n - 3 to 0, doing an O(1) operation each time.
    • This back traversal is done n - 3 times, also yielding a time complexity of O(n).
  3. Finding good indices:

    • We iterate through the range [k, n - k) and check two conditions for each index i, which again takes O(1) per index.
    • There are n - 2k such indices, leading this part to have a time complexity of O(n - 2k). However, since k is at most n, this simplifies to O(n).

Considering all three parts, the overall time complexity combines to:

  • O(n) + O(n) + O(n) = O(3n) which simplifies to O(n).

Space Complexity

  1. Space used by decr and incr arrays:

    • Both arrays have a size of n + 1, so the space taken by each is O(n).
    • Combined, they utilize 2 * (n + 1) memory space, which simplifies to O(2n) or just O(n).
  2. Space used for the output list:

    • In the worst-case scenario, every index from k to n - k may be a good index, so this list can take up to n - 2k spaces.
    • The worst case for this list is also when k is very small compared to n, which would make its space complexity approach O(n).

Therefore, combining the space complexities from the arrays and the final output list, we get:

  • O(n) + O(n) = O(2n) which simplifies to O(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.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What data structure does Breadth-first search typically uses to store intermediate states?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More