Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2420.html

2420. Find All Good Indices

• Difficulty: Medium.
• Related Topics: .
• Similar Questions: Find Good Days to Rob the Bank, Abbreviating the Product of a Range.

Problem

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^5

• 1 <= nums[i] <= 10^6

• 1 <= k <= n / 2

Solution (Java, C++, Python)

• Java
• C++
• Python
• Go

• class Solution {
      public List<Integer> goodIndices(int[] nums, int k) {
          int n = nums.length;
          int[] decr = new int[n];
          int[] incr = new int[n];
          Arrays.fill(decr, 1);
          Arrays.fill(incr, 1);
          for (int i = 2; i < n - 1; ++i) {
              if (nums[i - 1] <= nums[i - 2]) {
                  decr[i] = decr[i - 1] + 1;
              }
          }
          for (int i = n - 3; i >= 0; --i) {
              if (nums[i + 1] <= nums[i + 2]) {
                  incr[i] = incr[i + 1] + 1;
              }
          }
          List<Integer> ans = new ArrayList<>();
          for (int i = k; i < n - k; ++i) {
              if (decr[i] >= k && incr[i] >= k) {
                  ans.add(i);
              }
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      vector<int> goodIndices(vector<int>& nums, int k) {
          int n = nums.size();
          vector<int> decr(n, 1);
          vector<int> incr(n, 1);
          for (int i = 2; i < n; ++i) {
              if (nums[i - 1] <= nums[i - 2]) {
                  decr[i] = decr[i - 1] + 1;
              }
          }
          for (int i = n - 3; ~i; --i) {
              if (nums[i + 1] <= nums[i + 2]) {
                  incr[i] = incr[i + 1] + 1;
              }
          }
          vector<int> ans;
          for (int i = k; i < n - k; ++i) {
              if (decr[i] >= k && incr[i] >= k) {
                  ans.push_back(i);
              }
          }
          return ans;
      }
  };
  

• class Solution:
      def goodIndices(self, nums: List[int], k: int) -> List[int]:
          n = len(nums)
          decr = [1] * (n + 1)
          incr = [1] * (n + 1)
          for i in range(2, n - 1):
              if nums[i - 1] <= nums[i - 2]:
                  decr[i] = decr[i - 1] + 1
          for i in range(n - 3, -1, -1):
              if nums[i + 1] <= nums[i + 2]:
                  incr[i] = incr[i + 1] + 1
          return [i for i in range(k, n - k) if decr[i] >= k and incr[i] >= k]
  
  

• func goodIndices(nums []int, k int) []int {
  	n := len(nums)
  	decr := make([]int, n)
  	incr := make([]int, n)
  	for i := range decr {
  		decr[i] = 1
  		incr[i] = 1
  	}
  	for i := 2; i < n; i++ {
  		if nums[i-1] <= nums[i-2] {
  			decr[i] = decr[i-1] + 1
  		}
  	}
  	for i := n - 3; i >= 0; i-- {
  		if nums[i+1] <= nums[i+2] {
  			incr[i] = incr[i+1] + 1
  		}
  	}
  	ans := []int{}
  	for i := k; i < n-k; i++ {
  		if decr[i] >= k && incr[i] >= k {
  			ans = append(ans, i)
  		}
  	}
  	return ans
  }
  

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).

All Problems

All Solutions