Find All Good Indices

#56 Most AskedMedium

Find All Good Indices #56 Most Asked

Medium

ByteDance

7 views

Topics:

ArraysSliding Windows

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 <= 10⁵
1 <= nums[i] <= 10⁶
1 <= k <= n / 2

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the size of the `nums` array and the value of `k`?
Can the `nums` array contain negative numbers, zero, or floating-point numbers, or is it strictly positive integers?
If no good indices exist, should I return an empty list or null?
If `k` is greater than or equal to the length of `nums`, what should the expected output be?
Could you clarify the definition of 'non-increasing' and 'non-decreasing'? Does 'non-increasing' mean strictly decreasing, or is equality allowed?

Brute Force Solution

Approach

To solve this problem using the brute force strategy, we will examine each position in a list to determine if it is a 'good' one. For each position, we will independently check two things: whether the numbers to its left are non-increasing and whether the numbers to its right are non-decreasing.

Here's how the algorithm would work step-by-step:

Go through each position in the list, except for those near the very beginning or the very end because they won't have enough numbers to check on both sides.
For a position you are checking, look at the numbers to its immediate left. Are they in a non-increasing order (each number is the same or smaller than the one before it)?
If the numbers on the left are not in non-increasing order, then this position isn't 'good', so move on to the next position to check.
If the numbers on the left *are* in non-increasing order, now check the numbers to the immediate right of the position you are checking. Are they in a non-decreasing order (each number is the same or bigger than the one before it)?
If the numbers on the right are not in non-decreasing order, then this position also isn't 'good', so move on.
If the numbers on both the left and right *are* in the correct order, then this position *is* 'good'! Keep track of it.
Once you've gone through all possible positions, report all the 'good' positions that you found.

Code Implementation

def find_all_good_indices_brute_force(numbers, sub_array_length):
    good_indices = []
    list_length = len(numbers)

    for index_to_check in range(sub_array_length, list_length - sub_array_length):
        is_good_index = True

        # Check the descending condition.
        for preceding_index in range(index_to_check - sub_array_length, index_to_check - 1):
            if numbers[preceding_index] < numbers[preceding_index + 1]:
                is_good_index = False
                break

        # If the preceding numbers are not descending, continue.
        if not is_good_index:
            continue

        # Check the ascending condition.
        for following_index in range(index_to_check + 1, index_to_check + sub_array_length):
            if numbers[following_index] < numbers[following_index - 1]:
                is_good_index = False
                break

        # The current index is a 'good' index.
        if is_good_index:
            good_indices.append(index_to_check)

    return good_indices

Big(O) Analysis

Time Complexity

O(n*k) – The algorithm iterates through each index i from k to n-k-1, where n is the length of the input array nums and k is the given integer. For each such index i, it checks k elements to its left to ensure they are in non-increasing order, and k elements to its right to ensure they are in non-decreasing order. Therefore, for each index i, the algorithm performs approximately 2*k comparisons. Since this is done for approximately n indices, the overall time complexity is O(n*k).

Space Complexity

O(1) – The provided algorithm iterates through the input list and checks conditions at each position without using any auxiliary data structures that scale with the input size. It only uses a fixed number of variables to store the indices of 'good' positions, and potentially loop counters. Therefore, the auxiliary space complexity is constant, independent of the size of the input list (N).

Optimal Solution

Approach

The core idea is to precompute information about increasing and decreasing sequences. Instead of checking the condition for each possible index, we prepare ahead of time to quickly identify the 'good' ones.

Here's how the algorithm would work step-by-step:

Calculate, for each position, how many numbers before it form a non-increasing sequence.
Calculate, for each position, how many numbers after it form a non-decreasing sequence.
Go through each possible index, checking if the non-increasing sequence before it and the non-decreasing sequence after it are long enough.
If both sequences are long enough based on the given parameter, then the index is 'good'.

Code Implementation

def find_good_indices(numbers, sub_array_length):
    array_length = len(numbers)
    decreasing_counts = [0] * array_length

    # Calculate decreasing subsequence lengths from left.
    for i in range(1, array_length):
        if numbers[i] <= numbers[i - 1]:
            decreasing_counts[i] = decreasing_counts[i - 1] + 1

    increasing_counts = [0] * array_length

    # Calculate increasing subsequence lengths from right.
    for i in range(array_length - 2, -1, -1):
        if numbers[i] <= numbers[i + 1]:
            increasing_counts[i] = increasing_counts[i + 1] + 1

    good_indices = []

    # Iterate through possible good indices.
    for i in range(sub_array_length, array_length - sub_array_length):
        # Check if the index satisfies the conditions to be good.
        if decreasing_counts[i - 1] >= sub_array_length - 1 and \
           increasing_counts[i + 1] >= sub_array_length - 1:

            good_indices.append(i)

    return good_indices

Big(O) Analysis

Time Complexity

O(n) – The algorithm involves three main steps. First, calculating the lengths of non-increasing sequences before each index takes O(n) time. Second, calculating the lengths of non-decreasing sequences after each index also takes O(n) time. Finally, iterating through each index and checking if it's 'good' based on the precomputed lengths takes O(n) time. Therefore, the dominant factor is the linear traversal of the array, resulting in an overall time complexity of O(n).

Space Complexity

O(N) – The algorithm precomputes two arrays: one to store the lengths of non-increasing sequences before each index, and another for the lengths of non-decreasing sequences after each index. Both arrays have a size equal to the number of elements in the input array, which we denote as N. Therefore, the auxiliary space required is proportional to N, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty nums array	Return an empty list since a 'good' index cannot exist.
k is 0	Every index except the first and last k elements is a good index; return all indices from k to nums.length - k -1 inclusive.
k is greater than or equal to nums.length	Return an empty list since no index can have k elements before and after it.
nums.length is less than 2 * k + 1	Return an empty list since no index can have k elements before and after it.
Large nums array (performance)	Optimize the solution to avoid redundant calculations, potentially using dynamic programming to precompute non-increasing/non-decreasing sequences.
nums array with all identical values	All indices from k to nums.length - k - 1 (inclusive) will be good indices, as the sequences will always be non-increasing and non-decreasing.
Integer overflow during calculation if values in `nums` are very large/small, and k is large.	Use a data type that can accommodate larger numbers or check if any intermediate value exceeds the bounds.
k equals to nums.length/2, resulting to a single middle index	The algorithm must correctly identify whether the single middle index meets both the non-increasing and non-decreasing conditions, returning either a list with the index, or an empty list.

Empty nums array

How to Handle:

Return an empty list since a 'good' index cannot exist.

k is 0

How to Handle:

Every index except the first and last k elements is a good index; return all indices from k to nums.length - k -1 inclusive.

k is greater than or equal to nums.length

How to Handle:

Return an empty list since no index can have k elements before and after it.

nums.length is less than 2 * k + 1

How to Handle:

Return an empty list since no index can have k elements before and after it.

Large nums array (performance)

How to Handle:

Optimize the solution to avoid redundant calculations, potentially using dynamic programming to precompute non-increasing/non-decreasing sequences.

nums array with all identical values

How to Handle:

All indices from k to nums.length - k - 1 (inclusive) will be good indices, as the sequences will always be non-increasing and non-decreasing.

Integer overflow during calculation if values in `nums` are very large/small, and k is large.

How to Handle:

Use a data type that can accommodate larger numbers or check if any intermediate value exceeds the bounds.

k equals to nums.length/2, resulting to a single middle index

How to Handle:

The algorithm must correctly identify whether the single middle index meets both the non-increasing and non-decreasing conditions, returning either a list with the index, or an empty list.