Find All Good Indices
Problem 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:
1. The k elements that are just before the index i are in non-increasing order.
2. 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.
Examples
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.
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
The solution for the given problem statement can be solved using Brute force approach, prefix sum, etc. Each of the approaches has it's benefits and challenges regarding how fast it works and how much memory it uses.
Brute Force Approach
Intuition
The question simply asks us to store the indices of an array where k numbers to the left of that particular index are in decreasing order and k numbers to the right of it are in increasing order.
We will just traverse the array from i=k to i=n-k. We will then check the k left numbers and then the k right numbers with respect to the index we choose.
How to check whether the k left elements are sorted in decreasing order ?
For the elements to the left of index i, we will iterate from i-k to i-1 and ensure each element is strictly greater than the next element.
We will maintain a boolean variable "isDec" initialized to true which will let us know whether the k left numbers are sorted or not after the traversal.
While comparing two adjacent numbers, if nums[j] > nums[j - 1] , we will assign false to isDec showing that ,we encountered a increasing order of numbers.
How to check whether the k right elements are sorted in decreasing order ?
For the elements to the left of index i, we will iterate from i+1 to i+k and ensure each element is strictly greater than the next element.
We will maintain a boolean variable "isInc" initialized to true which will let us know whether the k right numbers are sorted or not after the traversal.
While comparing two adjacent numbers, if nums[j] > nums[j + 1] , we will assign false to isInc showing that ,we encountered a decreasing order of numbers.
If the k left numbers are in decreasing order and the k right numbers are in increasing order, we will add that particular index to our resultant array.
We will return the array once we traverse the complete list.
Approach
Initialize Variables: Create an empty list to store "good indices."Let n be the length of the input array.
Iterate Over the Potential Indices: For each index i starting from k to n - k - 1:Initialize two flags, dec (decreasing) and inc (increasing), both set to true.
Check for Non-Increasing Sequence Before i: For every pair of consecutive elements from i - 1 to i - k:If any element is smaller than the next element:Set dec to false.Break out of the loop.
Check for Non-Decreasing Sequence After i: For every pair of consecutive elements from i + 1 to i + k:If any element is greater than the next element:Set inc to false.Break out of the loop.
Add Index to List if Both Conditions are True: If both dec and inc are true:Add i to the list of "good indices."
Return the List of Good Indices: Return the list as the result.
Dry-Run
nums = [4, 3, 2, 1, 1, 2, 3, 1]
k = 2
Output:- [2,3,4]
Initialize:
- goodIndices = []
- n = 8
Loop: Iterate over i from k to n - k (i.e., i ranges from 2 to 5)
Iteration 1: i = 2
- Check for non-increasing sequence from i-1 to i-k:
Subarray: [4, 3] - 4 >= 3 → True
- Non-increasing condition satisfied.
- Check for non-decreasing sequence from i+1 to i+k:
Subarray: [1, 2] - 1 <= 2 → True
- Non-decreasing condition satisfied.
- Both conditions satisfied.
Add i = 2 to goodIndices.
goodIndices = [2].
Iteration 2: i = 3
- Check for non-increasing sequence from i-1 to i-k:
Subarray: [3, 2] - 3 >= 2 → True
- Non-increasing condition satisfied.
- Check for non-decreasing sequence from i+1 to i+k:
Subarray: [1, 2] - 1 <= 2 → True
- Non-decreasing condition satisfied.
- Both conditions satisfied.
Add i = 3 to goodIndices.
goodIndices = [2, 3].
Iteration 3: i = 4
- Check for non-increasing sequence from i-1 to i-k:
Subarray: [2, 1] - 2 >= 1 → True
- Non-increasing condition satisfied.
- Check for non-decreasing sequence from i+1 to i+k:
Subarray: [2, 3] - 2 <= 3 → True
- Non-decreasing condition satisfied.
- Both conditions satisfied.
Add i = 4 to goodIndices.
goodIndices = [2, 3, 4].
Iteration 4: i = 5
- Check for non-increasing sequence from i-1 to i-k:
Subarray: [1, 1] - 1 >= 1 → True
- Non-increasing condition satisfied.
- Check for non-decreasing sequence from i+1 to i+k:
Subarray: [3, 1] - 3 > 1 → False
- Non-decreasing condition NOT satisfied.
- Skip adding i = 5.
Brute Force Code in all Languages.
1. C++ Try on Compiler
class Solution {
public:
vector<int> goodIndices(vector<int>& nums, int k) {
// Initialize a vector to store the result indices
vector<int> goodIndices;
int n = nums.size();
// Iterate through the array, starting from index k to n-k
for (int i = k; i < n - k; i++) {
// Flags to check non-increasing and non-decreasing conditions
bool dec = true, inc = true;
// Check the k elements before the current index for non-increasing order
for (int j = i - 1; j > i - k; j--) {
if (nums[j] > nums[j - 1]) {
dec = false;
break;
}
}
// Check the k elements after the current index for non-decreasing order
for (int j = i + 1; j < i + k; j++) {
if (nums[j] > nums[j + 1]) {
inc = false;
break;
}
}
// Add the index to the result if both conditions are satisfied
if (inc && dec) {
goodIndices.push_back(i);
}
}
// Return the list of good indices
return goodIndices;
}
};
2. Java Try on Compiler
class Solution {
public List<Integer> goodIndices(int[] nums, int k) {
// Initialize a list to store the result indices
List<Integer> goodIndices = new ArrayList<>();
int n = nums.length;
// Iterate through the array, starting from index k to n-k
for (int i = k; i < n - k; i++) {
// Flags to check non-increasing and non-decreasing conditions
boolean dec = true, inc = true;
// Check the k elements before the current index for non-increasing order
for (int j = i - 1; j > i - k; j--) {
if (nums[j] > nums[j - 1]) {
dec = false;
break;
}
}
// Check the k elements after the current index for non-decreasing order
for (int j = i + 1; j < i + k; j++) {
if (nums[j] > nums[j + 1]) {
inc = false;
break;
}
}
// Add the index to the result if both conditions are satisfied
if (inc && dec) {
goodIndices.add(i);
}
}
// Return the list of good indices
return goodIndices;
}
}
3. Python Try on Compiler
class Solution:
def goodIndices(self, nums, k):
# Initialize a list to store the result indices
good_indices = []
n = len(nums)
# Iterate through the array, starting from index k to n-k
for i in range(k, n - k):
# Flags to check non-increasing and non-decreasing conditions
dec = True
inc = True
# Check the k elements before the current index for non-increasing order
for j in range(i - 1, i - k, -1):
if nums[j] > nums[j - 1]:
dec = False
break
# Check the k elements after the current index for non-decreasing order
for j in range(i + 1, i + k):
if nums[j] > nums[j + 1]:
inc = False
break
# Add the index to the result if both conditions are satisfied
if dec and inc:
good_indices.append(i)
# Return the list of good indices
return good_indices
4. JavaScript Try on Compiler
var goodIndices = function(nums, k) {
// Initialize an array to store the result indices
let goodIndices = [];
let n = nums.length;
// Iterate through the array, starting from index k to n-k
for (let i = k; i < n - k; i++) {
// Flags to check non-increasing and non-decreasing conditions
let dec = true, inc = true;
// Check the k elements before the current index for non-increasing order
for (let j = i - 1; j > i - k; j--) {
if (nums[j] > nums[j - 1]) {
dec = false;
break;
}
}
// Check the k elements after the current index for non-decreasing order
for (let j = i + 1; j < i + k; j++) {
if (nums[j] > nums[j + 1]) {
inc = false;
break;
}
}
// Add the index to the result if both conditions are satisfied
if (inc && dec) {
goodIndices.push(i);
}
}
// Return the list of good indices
return goodIndices;
};Time Complexity: O(n x k)
The function iterates through all indices i in the range [k,n−k). For each i, it performs the following operations: (k inclusive, n-k exclusive)
- Checking the decreasing subarray condition:
The inner loop iterates k times from i−1 to i−k.
Time complexity for this part is O(k). - Checking the increasing subarray condition:
The inner loop iterates k times from i+1 to i+k.
Time complexity for this part is O(k).
Thus, for each iii, the work done is O(k)+O(k)=O(2k), which simplifies to O(k). Since the outer loop runs for approximately n−2k iterations, the overall time complexity is: O((n−2k)⋅k) = O(nk ⋅ 2k^2)
For large n and k, this simplifies to: O(n⋅k)
Therefore, the overall time complexity is : O(n⋅k)
Space Complexity: O(1)
Auxiliary Space Complexity refers to the extra space or temporary memory that an algorithm uses during its execution, excluding the space required for the input data.The algorithm uses constant extra space apart from the list goodIndices:
- Variables: n, dec, inc, and loop counters require O(1) space.
- List goodIndices: At most n indices can be added to the list. Hence, the space required for goodIndices is O(n). However, this is not included in the auxiliary space
Thus, the auxiliary space complexity is: O(1)
Total Space Complexity
The total space complexity accounts for both the input and auxiliary space:
- Input array nums: Requires O(n) space.
- Auxiliary space: O(n) for goodIndices and O(1) for variables.
Adding these, the total space complexity is: O(n)+O(n)=O(n)
Reviewing the constraints for the given question which is "3 <= nums.length <= 10^5" will result in Time Limit Exceeded for the Brute Force Approach.
The interviewer will be unhappy with the approach, we need to figure out an optimal solution.
What challenges did we face in the Brute Force Approach ?
Redundancy of Checks:
- To verify if the k elements before and after every index satisfy the required conditions, the brute force approach repeatedly iterates over overlapping subarrays.
- This repetition leads to inefficiency, especially for large arrays.
Poor Scalability:
- Time complexity is O(n × k) in the brute force approach, making it slow for large arrays.
Optimal Approach
Intuition
Once we gather the insights and the challenges faced in the Brute Force Algorithm.
Our Brute Force algorithm was slower because of Repeated checks and Poor Scalability for larger sized arrays.
Let's address the first issue where we need to optimize, which is "Repeated checks".
Repeated checks ??Are we saying that some part is overlapping which means something is re-calculated over and over again !!
Yes, the terms "overlapping" ,"re-calculate" or "repeating" give us the intuition of the prefix sum approach.
Let's now see , how can we proceed with our intuition.
The non-increasing condition for the k elements before i(the pivot index):If at an index j, the k elements up to j are non-increasing, then this property can be extended to the next index if nums[j] >= nums[j+1].For example:In nums = [4, 3, 2, 1], if nums[2] satisfies the condition for a subarray of size 3, then extending to nums[3] depends only on whether nums[3] <= nums[2].
Similarly, the non-decreasing condition for the k elements after i:If at an index j, the k elements starting from j are non-decreasing, then this property can be extended to the previous index if nums[j] >= nums[j-1].For example:In nums = [1, 2, 3, 4], if nums[2] satisfies the condition for a subarray of size 3, then extending backwards to nums[1] depends only on whether nums[1] <= nums[2].
Yes !! Instead of repeatedly checking overlapping subarrays, we can precompute how far the conditions hold.
So, to achieve this we can make use of two arrays mainly the left[] and the right[] arrays,
Left array (left[]): left[i] stores the length of the longest non-increasing subarray ending at i.
Right array (right[]): right[i] stores the length of the longest non-decreasing subarray starting at i.
This allows us to check conditions in constant time during the main loop.
By maintaining left[] and right[], we avoid recalculating the same subarray properties multiple times. Instead of performing O(k) operations for every index, we preprocess left[] and right[] in O(n) time which earlier took O(n x k) time. We will be able to access the values in O(1) runtime since the pre-computed values are stored in the prefix array and we have to access the particular indexed value. Hence, the pre-computation of the left[] and the right[] is optimal.
How the left[] is computed ?
Start with the first element (i = 0): A single element forms a non-increasing subarray, so left[0] = 1.
For every other index i:
- If nums[i] <= nums[i-1], extend the non-increasing subarray from i-1:
- left[i] = left[i-1] + 1.
- Otherwise, reset to 1 because the condition is violated:
- left[i] = 1.
Key Idea: At each i, we store how far back the array remains non-increasing.
How the right[] is computed ?
Start with the last element (i = n-1): A single element forms a non-decreasing subarray, so right[n-1] = 1.
For every other index i (moving backward):
- If nums[i] <= nums[i+1], extend the non-decreasing subarray from i+1:
- right[i] = right[i+1] + 1.
- Otherwise, reset to 1 because the condition is violated:
- right[i] = 1.
Key Idea: At each i, we store how far forward the array remains non-decreasing.
Once the precomputations are done, validating whether an index is "good" becomes a simple comparison: We will simply check left[i-1] >= k and right[i+1] >= k.
How the formula "left[i-1] >= k and right[i+1] >= k " works ?
left[i-1] >= k ensures that the k elements ending at i-1 are non-increasing.
right[i+1] >= k ensures that the k elements after i+1 are non-decreasing.
Approach
Step 1: Initialize left[ ] Array: Create an array left of size n initialized to 1.
- For i from 1 to n-1:
- If nums[i-1] >= nums[i]: left[i] = left[i-1] + 1.
- Else: left[i] = 1.
Step 2: Initialize right[ ] Array: Create an array right of size n initialized to 1.
- For i from n-2 to 0:
- If nums[i] <= nums[i+1]: right[i] = right[i+1] + 1.
- Else: right[i] = 1.
Step 3: Check for Good Indices: Initialize an empty list goodIndices.
- For i from k to n-k-1: If left[i-1] >= k and right[i+1] >= k: Add i to goodIndices.
Step 4: Return Result: Return the list goodIndices.
Dry-Run
nums = [4, 3, 2, 1, 1, 2, 3, 1]
k = 2
Output:- [2,3,4]
Step 1: Compute the left[ ] ArrayInitialization:
left[0] = 1 (a single element forms a non-increasing subarray).
Iteration:
- i = 1:
nums[0] >= nums[1] → 4 >= 3.
left[1] = left[0] + 1 = 2. - i = 2:
nums[1] >= nums[2] → 3 >= 2.
left[2] = left[1] + 1 = 3. - i = 3:
nums[2] >= nums[3] → 2 >= 1.
left[3] = left[2] + 1 = 4. - i = 4:
nums[3] >= nums[4] → 1 >= 1.
left[4] = left[3] + 1 = 5. - i = 5:
nums[4] < nums[5] → 1 < 2.
left[5] = 1. - i = 6:
nums[5] < nums[6] → 2 < 3.
left[6] = 1. - i = 7:
nums[6] > nums[7] → 3 > 1.
left[7] = 1.
Final left[ ]:
left = [1, 2, 3, 4, 5, 1, 1, 1]
Step 2: Compute the right[ ] ArrayInitialization:
right[7] = 1 (a single element forms a non-decreasing subarray).
Iteration:
- i = 6:
nums[6] >= nums[7] → 3 >= 1.
right[6] = right[7] + 1 = 1. - i = 5:
nums[5] <= nums[6] → 2 <= 3.
right[5] = right[6] + 1 = 2. - i = 4:
nums[4] <= nums[5] → 1 <= 2.
right[4] = right[5] + 1 = 3. - i = 3:
nums[3] <= nums[4] → 1 <= 1.
right[3] = right[4] + 1 = 4. - i = 2:
nums[2] > nums[3] → 2 > 1.
right[2] = 1. - i = 1:
nums[1] < nums[2] → 3 < 2.
right[1] = 1. - i = 0:
nums[0] < nums[1] → 4 < 3.
right[0] = 1.
Final right[ ]:
right = [1, 1, 1, 4, 3, 2, 1, 1]
Step 3: Find Good IndicesCondition:
- For i from k to n-k-1:
- left[i-1] >= k and right[i+1] >= k.
Check Each Index:
- i = 2:
left[1] = 2 >= 2 and right[3] = 4 >= 2.
Add i = 2 to the result. - i = 3:
left[2] = 3 >= 2 and right[4] = 3 >= 2.
Add i = 3 to the result. - i = 4:
left[3] = 4 >= 2 and right[5] = 2 >= 2.
Add i = 4 to the result. - i = 5:
left[4] = 5 >= 2 and right[6] = 1 < 2.
Skip i = 5.
Final Result:
Good indices: [2, 3, 4]
Optimal Code in all Languages.
1. C++ Try on Compiler
class Solution {
public:
vector<int> goodIndices(vector<int>& nums, int k) {
int n = nums.size();
vector<int> left(n, 1), right(n, 1), result;
// Compute the 'left' array to store the length of non-increasing subarrays ending at each index
for (int i = 1; i < n; i++) {
if (nums[i - 1] >= nums[i])
left[i] = left[i - 1] + 1; // Increment length if non-increasing
}
// Compute the 'right' array to store the length of non-decreasing subarrays starting at each index
for (int i = n - 2; i >= 0; i--) {
if (nums[i] <= nums[i + 1])
right[i] = right[i + 1] + 1; // Increment length if non-decreasing
}
// Identify good indices based on the conditions
for (int i = k; i < n - k; i++) {
// Check if the k elements before index i are non-increasing
// and the k elements after index i are non-decreasing
if (left[i - 1] >= k && right[i + 1] >= k)
result.push_back(i);
}
return result;
}
};2. Java Try on Compiler
class Solution {
public List<Integer> goodIndices(int[] nums, int k) {
int n = nums.length;
int[] left = new int[n];
int[] right = new int[n];
List<Integer> result = new ArrayList<>();
// Initialize left and right arrays
left[0] = 1;
right[n - 1] = 1;
// Compute left array
for (int i = 1; i < n; i++) {
if (nums[i - 1] >= nums[i]) {
left[i] = left[i - 1] + 1;
} else {
left[i] = 1;
}
}
// Compute right array
for (int i = n - 2; i >= 0; i--) {
if (nums[i] <= nums[i + 1]) {
right[i] = right[i + 1] + 1;
} else {
right[i] = 1;
}
}
// Check for good indices
for (int i = k; i < n - k; i++) {
if (left[i - 1] >= k && right[i + 1] >= k) {
result.add(i);
}
}
return result;
}
}
3. Python Try on Compiler
class Solution:
def goodIndices(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
left = [1] * n
right = [1] * n
result = []
# Compute left array
for i in range(1, n):
if nums[i - 1] >= nums[i]:
left[i] = left[i - 1] + 1
# Compute right array
for i in range(n - 2, -1, -1):
if nums[i] <= nums[i + 1]:
right[i] = right[i + 1] + 1
# Check for good indices
for i in range(k, n - k):
if left[i - 1] >= k and right[i + 1] >= k:
result.append(i)
return result
4. JavaScript Try on Compiler
var goodIndices = function(nums, k) {
const n = nums.length;
const left = Array(n).fill(1);
const right = Array(n).fill(1);
const result = [];
// Compute left array
for (let i = 1; i < n; i++) {
if (nums[i - 1] >= nums[i]) {
left[i] = left[i - 1] + 1;
}
}
// Compute right array
for (let i = n - 2; i >= 0; i--) {
if (nums[i] <= nums[i + 1]) {
right[i] = right[i + 1] + 1;
}
}
// Check for good indices
for (let i = k; i < n - k; i++) {
if (left[i - 1] >= k && right[i + 1] >= k) {
result.push(i);
}
}
return result;
};
Time Complexity: O(n)
- Left Array Calculation:
- We iterate through the array once (for loop) to fill the left array.
- Time complexity: O(n).
- Right Array Calculation:
- We iterate through the array once in reverse to fill the right array.
- Time complexity: O(n).
- Finding Good Indices:
- We iterate through the array to check the conditions for "good indices."
- Time complexity: O(n).
Overall Time Complexity:
Since all operations are sequential and O(n), the total time complexity is: O(n)
Space Complexity: O(n)
Auxiliary Space Complexity refers to the amount of extra or temporary memory used by an algorithm during its execution, excluding the memory required to store the input and output data.
- Left Array:
- Requires O(n) space to store the length of the non-increasing subarray ending at each index.
- Right Array:
- Requires O(n) space to store the length of the non-decreasing subarray starting at each index.
- Result List:
- In the worst case, all indices could be good indices, so the list could grow up to O(n). However, this does not count as auxiliary space if we include it in total space.
Auxiliary Space Complexity:
The algorithm uses two auxiliary arrays (left and right), each of size O(n), making the total: O(n) + O(n) = O(2n) = O(n)
Total Space Complexity
- Input Array:
- The input array nums has size O(n).
- Auxiliary Space:
- O(n) space for left and O(n) space for right.
- Result List:
- The output list could potentially hold O(n) indices in the worst case.
Total Space Complexity:
Combining input size O(n), auxiliary arrays O(n), and the output list O(n).
The overall total space complexity is O(n)+O(n) = O(2n) = O(n).
Learning Tip
You and a gang of thieves are planning on robbing a bank. You are given a 0-indexed integer array security, where security[i] is the number of guards on duty on the ith day. The days are numbered starting from 0. You are also given an integer time.
The ith day is a good day to rob the bank if:
- There are at least time days before and after the ith day,
- The number of guards at the bank for the time days before i are non-increasing, and
- The number of guards at the bank for the time days after i are non-decreasing.
More formally, this means day i is a good day to rob the bank if and only if security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... <= security[i + time - 1] <= security[i + time].
Return a list of all days (0-indexed) that are good days to rob the bank. The order that the days are returned in does not matter.
You may recall that an array arr is a mountain array if and only if:
- arr.length >= 3
- There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
- arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
- arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Given an integer array arr, return the length of the longest subarray, which is a mountain. Return 0 if there is no mountain subarray.