3006. Find Beautiful Indices in the Given Array I - Detailed Explanation

Problem Statement

Given an integer array nums and a positive integer k, an index i (0-indexed) is defined as beautiful if both of the following conditions are met:

1. There are at least k elements to the left and at least k elements to the right of index i. In other words, index i is valid only if i - k ≥ 0 and i + k < nums.length.
2. The subarray of k elements immediately to the left of i (i.e. from nums[i - k] to nums[i - 1]) is non-decreasing (each element is less than or equal to the next).
3. The subarray of k elements immediately to the right of i (i.e. from nums[i + 1] to nums[i + k]) is non-increasing (each element is greater than or equal to the next).

The goal is to determine the number of beautiful indices in the given array.

Example Inputs, Outputs, and Explanations

Example 1

Input:

nums = [1, 2, 3, 3, 2, 1]
k = 2

Output:

2

Explanation:

• For i = 2 (nums[2] = 3):
  • Left subarray: [1, 2] is non-decreasing.
  • Right subarray: [3, 2] is non-increasing (3 ≥ 2).
• For i = 3 (nums[3] = 3):
  • Left subarray: [2, 3] is non-decreasing.
  • Right subarray: [2, 1] is non-increasing (2 ≥ 1).

Both indices 2 and 3 satisfy the conditions.

Example 2

Input:

nums = [1, 1, 1, 1, 1]
k = 1

Output:

3

Explanation:
Valid indices are 1, 2, and 3 because:

• For any such index, the one element to the left and the one element to the right (when they exist) trivially satisfy the monotonicity conditions (a single element subarray is always non-decreasing or non-increasing).

Example 3

Input:

nums = [3, 2, 1, 4, 5, 4, 3]
k = 2

Output:

1

Explanation:

• Index 4 (nums[4] = 5):
  • Left subarray: [1, 4] is non-decreasing.
  • Right subarray: [4, 3] is non-increasing. Other potential indices either do not have enough elements on both sides or fail the monotonicity check.

Constraints

• The length of nums is at least 2 * k + 1 (to ensure there exists at least one index with k elements on both sides).
• k is a positive integer.
• The elements of nums can be any integers.

Hints for the Approach

1. Brute Force Verification:
   For each valid index i (i.e., where i - k ≥ 0 and i + k < nums.length), you can scan the subarrays to the left and right to check if they meet the monotonicity conditions. However, this approach may lead to an overall time complexity of O(n * k), which can be inefficient for large arrays.

2. Precomputation with Prefix and Suffix Arrays:
   To efficiently check the monotonicity conditions, precompute:

   • A left array where left[i] is the length of the longest non-decreasing subarray ending at index i.
   • A right array where right[i] is the length of the longest non-increasing subarray starting at index i.

   Then, for each index i (with valid boundaries), you can quickly determine if:

   • left[i - 1] ≥ k (ensuring the left subarray is non-decreasing), and
   • right[i + 1] ≥ k (ensuring the right subarray is non-increasing).

Approach 1: Brute Force

Explanation

• Idea: For every valid index i, check the k elements to its left and right using simple loops.
• Procedure:
  • Iterate i from k to nums.length - k - 1.
  • For each index, loop through the left subarray (from i - k to i - 1) to verify it is non-decreasing.
  • Similarly, loop through the right subarray (from i + 1 to i + k) to verify it is non-increasing.
• Drawback:
  This method may become inefficient when the array is large since each index requires O(k) work.

Approach 2: Precomputation Using Prefix and Suffix Arrays

Explanation

1. Precompute Left Array:

   • Initialize an array left of the same size as nums.
   • left[0] is set to 1.
   • For every i from 1 to nums.length - 1:
     • If nums[i - 1] ≤ nums[i], then left[i] = left[i - 1] + 1; otherwise, left[i] = 1.
   • This array tells you the number of consecutive elements ending at i that form a non-decreasing subarray.

2. Precompute Right Array:

   • Initialize an array right of the same size as nums.
   • right[nums.length - 1] is set to 1.
   • For every i from nums.length - 2 down to 0:
     • If nums[i] ≥ nums[i + 1], then right[i] = right[i + 1] + 1; otherwise, right[i] = 1.
   • This array tells you the number of consecutive elements starting at i that form a non-increasing subarray.

3. Count Beautiful Indices:

   • Iterate over each valid index i (from k to nums.length - k - 1).
   • Check if left[i - 1] ≥ k and right[i + 1] ≥ k.
   • If both conditions hold, increment your beautiful index count.

Complexity Analysis

• Time Complexity:

  • Precomputation of the left and right arrays takes O(n) time.

  • Checking each valid index takes O(n) time.

  • Overall, the solution runs in O(n) time.

• Space Complexity:

  • O(n) space is required for the left and right arrays.

Code Implementation

Python Code