Leetcode 2420: Find All Good Indices
Given an integer array nums of size n and a positive integer k, find all good indices in the array. An index i is considered good if: The k elements just before it are in non-increasing order, and the k elements just after it are in non-decreasing order. Return a list of all good indices in increasing order.
Problem
Approach
Steps
Complexity
Input: You are given an array nums of integers and a positive integer k.
Example: nums = [3,2,2,2,5,6,2], k = 2
Constraints:
• 3 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^6
• 1 <= k <= n / 2
Output: Return an array containing all good indices sorted in increasing order.
Example: Output: [2, 3]
Constraints:
Goal: Identify the indices where the k elements before and after it satisfy the non-increasing and non-decreasing conditions, respectively.
Steps:
• 1. Initialize two arrays dp1 and dp2, where dp1 tracks the length of non-increasing subsequences before each index and dp2 tracks non-decreasing subsequences after each index.
• 2. Traverse the array to fill dp1 and dp2.
• 3. Loop through the indices from k to n-k and check the conditions for good indices.
• 4. Collect and return the indices that satisfy the conditions.
Goal: The solution should work efficiently even for large arrays, up to 100,000 elements.
Steps:
• Ensure the algorithm handles large arrays of up to 100,000 elements efficiently.
Assumptions:
• The array will contain at least 3 elements, and the value of k will be such that k <= n / 2.
• Input: Input: nums = [3, 2, 2, 2, 5, 6, 2], k = 2
• Explanation: Indices 2 and 3 are good because the elements before them form non-increasing sequences and the elements after them form non-decreasing sequences.
Approach: The solution involves filling two arrays (dp1 and dp2) to track the lengths of non-increasing and non-decreasing subsequences. The final step is checking which indices satisfy the good index conditions.
Observations:
• We need to efficiently track sequences of non-increasing and non-decreasing elements.
• We can use dynamic programming to build the dp1 and dp2 arrays and check for good indices by iterating over the array.
Steps:
• 1. Initialize two dp arrays: dp1 for non-increasing subsequences before each index and dp2 for non-decreasing subsequences after each index.
• 2. Loop through the array to fill dp1 and dp2.
• 3. Iterate through the array from index k to n-k and check if dp1[i-1] and dp2[i+1] are greater than or equal to k.
• 4. Return all such indices as the result.
Empty Inputs:
• The problem guarantees that n will be at least 3, so this case does not need to be handled.
Large Inputs:
• The algorithm should handle the maximum input size (up to 100,000 elements) efficiently.
Special Values:
• If no indices satisfy the conditions, return an empty array.
Constraints:
• Ensure the solution runs within time limits for large inputs (O(n) time complexity).
vector<int> goodIndices(vector<int>& a, int k) {
int n = a.size();
vector<int> dp1(n + 1, 1), dp2(n + 1, 1), ans;
for(int i = 1; i < n; i++)
if(a[i -1] >= a[i]) dp1[i] = dp1[i - 1]+1;
for(int i = n -2; i > 0; i--)
if(a[i] <= a[i +1]) dp2[i] = dp2[i +1]+1;
for(int i = k; i< n-k; i++)
if(dp1[i-1] >= k && dp2[i+1] >=k)
ans.push_back(i);
return ans;
}
1 : Function Declaration
vector<int> goodIndices(vector<int>& a, int k) {
This line defines the function 'goodIndices', which takes a vector of integers 'a' and an integer 'k'. It returns a vector of integers representing the indices where the condition holds.
2 : Variable Initialization
int n = a.size();
This line initializes 'n' to store the size of the input vector 'a'.
3 : Dynamic Programming Arrays Initialization
vector<int> dp1(n + 1, 1), dp2(n + 1, 1), ans;
Here, two dynamic programming arrays, 'dp1' and 'dp2', are initialized to size 'n + 1' with all elements set to 1. 'dp1' will track the length of decreasing subsequences from the left, while 'dp2' will track increasing subsequences from the right. The vector 'ans' will store the valid indices.
4 : First Loop
for(int i = 1; i < n; i++)
This loop iterates over the array starting from the second element (index 1). It updates the 'dp1' array based on whether the current element is less than or equal to the previous one.
5 : Update dp1
if(a[i -1] >= a[i]) dp1[i] = dp1[i - 1]+1;
If the current element 'a[i]' is less than or equal to the previous element 'a[i-1]', 'dp1[i]' is updated to the value of 'dp1[i-1]' + 1, indicating the continuation of a decreasing subsequence.
6 : Second Loop
for(int i = n -2; i > 0; i--)
This loop iterates over the array from the second last element to the second element. It calculates the 'dp2' array based on the condition of the next element being greater than or equal to the current element.
7 : Update dp2
if(a[i] <= a[i +1]) dp2[i] = dp2[i +1]+1;
If the current element 'a[i]' is less than or equal to the next element 'a[i+1]', 'dp2[i]' is updated to the value of 'dp2[i+1]' + 1, indicating the continuation of an increasing subsequence.
8 : Third Loop
for(int i = k; i< n-k; i++)
This loop iterates over indices 'i' from 'k' to 'n-k', ensuring that we have enough elements on both sides of the current index for comparison.
9 : Condition for Valid Indices
if(dp1[i-1] >= k && dp2[i+1] >=k)
This condition checks if the current index 'i' can form a valid index based on the lengths of the decreasing subsequence before it (dp1[i-1]) and the increasing subsequence after it (dp2[i+1]). Both need to be greater than or equal to 'k'.
10 : Store Valid Indices
ans.push_back(i);
If the index satisfies the condition, it is added to the 'ans' vector.
11 : Return
return ans;
The function returns the 'ans' vector, which contains all the valid indices.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) because we only traverse the array a few times.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) because we use two additional arrays (dp1 and dp2) of size n.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus