LeetCode 2420. Find All Good Indices Solution in Java, C++, Python & Go | Explanation + Code

Description

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 <= 105
• 1 <= nums[i] <= 106
• 1 <= k <= n / 2

Solutions

Solution 1: Recursion

We define two arrays decr and incr, which represent the longest non-increasing and non-decreasing subarray lengths from left to right and from right to left, respectively.

We traverse the array, updating the decr and incr arrays.

Then we sequentially traverse the index i (where k\le i \lt n - k), if decr[i] ≥ k and incr[i] ≥ k, then i is a good index.

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array.

PythonJavaC++Go

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](code-box)

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; } }(code-box)

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; } };(code-box)

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 }(code-box)