We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find All Good Indices

Number: 2504

Difficulty: Medium

Paid? No

Companies: ByteDance, Goldman Sachs

Problem Description

Given an integer array nums and a positive integer k, an index i (where k <= i < n - k) is considered good if:

  • The k elements immediately before index i form a non-increasing sequence.
  • The k elements immediately after index i form a non-decreasing sequence. Return all such good indices sorted in increasing order.

Key Insights

  • Use two auxiliary arrays to keep track of contiguous segments:
    • One for non-increasing segments ending at each index.
    • One for non-decreasing segments starting at each index.
  • For an index i to be good, ensure that:
    • The count of non-increasing elements ending at i-1 is at least k.
    • The count of non-decreasing elements starting at i+1 is at least k.
  • This approach allows checking conditions in O(1) per index after precomputation.

Space and Time Complexity

Time Complexity: O(n) where n is the length of nums, because we traverse the array a few times. Space Complexity: O(n) due to the auxiliary arrays used for storing contiguous segment lengths.

Solution

We solve this problem by precomputing two arrays:

  1. A left array where left[i] holds the length of the longest contiguous non-increasing subarray ending at i.
  2. A right array where right[i] holds the length of the longest contiguous non-decreasing subarray starting at i.

For the left array:

  • Set left[0] = 1.
  • For each i from 1 to n-1, if nums[i] <= nums[i-1], then left[i] = left[i-1] + 1; otherwise, reset left[i] = 1.

For the right array:

  • Set right[n-1] = 1.
  • For each i from n-2 down to 0, if nums[i] <= nums[i+1], then right[i] = right[i+1] + 1; otherwise, reset right[i] = 1.

Finally, iterate over indices i in the range [k, n-k) and check:

  • If left[i-1] >= k and right[i+1] >= k, then index i is good. Return the list of all such good indices.

Code Solutions

# Python solution for Find All Good Indices

def goodIndices(nums, k):
    n = len(nums)
    # Arrays to store the length of the contiguous segments
    left = [1] * n  # non-increasing sequence ending at each index
    right = [1] * n  # non-decreasing sequence starting at each index

    # Build the left array for non-increasing subarray
    for i in range(1, n):
        if nums[i] <= nums[i - 1]:
            left[i] = left[i - 1] + 1
        # else, left[i] remains 1
    # Build the right array for non-decreasing subarray
    for i in range(n - 2, -1, -1):
        if nums[i] <= nums[i + 1]:
            right[i] = right[i + 1] + 1
        # else, right[i] remains 1

    good_indices = []
    # Iterate over possible indices that can be good indices
    for i in range(k, n - k):
        # Check whether k-length segment before is non-increasing and after is non-decreasing
        if left[i - 1] >= k and right[i + 1] >= k:
            good_indices.append(i)
    return good_indices

# Example usage:
print(goodIndices([2,1,1,1,3,4,1], 2))  # Output: [2, 3]
← Back to All Questions