Leetcode Problem 2420. Find All Good Indices

2420. Find All Good Indices

Leetcode Solutions

DP Two passes O(n) solution

  1. Initialize two arrays left and right of length n to store the lengths of the longest non-increasing and non-decreasing subsequences respectively.
  2. Set count to 1 and iterate through nums from index 1 to n-1:
    • If nums[i] <= nums[i-1], increment count, else reset count to 1.
    • If count is at least k, set left[i] to True.
  3. Reset count to 1 and iterate through nums from index n-2 to 0:
    • If nums[i] <= nums[i+1], increment count, else reset count to 1.
    • If count is at least k, set right[i] to True.
  4. Initialize an empty list good_indices.
  5. Iterate through the range k to n-k and add the index i to good_indices if both left[i] and right[i] are True.
  6. Return good_indices.
UML Thumbnail

Sliding Window Approach

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...