# 2420\. Find All Good Indices

https://leetcode.com/problems/find-all-good-indices/discuss/2624427/Keep-the-index-of-last-bad-relationship-and-utilize-the-symmetry.

"""
TLE
"""

def non_increasing(li, k):
    for i in range(1,k):  # len(li) will be same as k
        if li[i-1] < li[i]:
            return False
    return True
    
def non_decreasing(li, k):
    for i in range(1,k):  # len(li) will be same as k
        if li[i-1] > li[i]:
            return False
    return True

class Solution:
    def goodIndices(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        if n <= 2 * k:
            return []
        
        ans = []
        for i in  range(k, n - k):
            if non_increasing(nums[i - k:i], k) and non_decreasing(nums[i + 1:i + 1 + k], k):
                ans.append(i)
                
        return ans 

#############################################################################################
    
class Solution:
    def goodIndices(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        
        # previous k non-increasing
        last_idx_larger_than_prev = None  # Record last i such that nums[i-1] < nums[i]
        previous_k_non_incr = [True] * n
        for i in range(n):
            if i == 0:
                continue
            
            # If the bad relationship (nums[i-1]<nums[i]) is too near,
            # it fails to meet:
            # "The k elements that are just before the index i are in non-increasing order."
            if last_idx_larger_than_prev is not None \
            and last_idx_larger_than_prev >= i - k + 1:
                previous_k_non_incr[i] = False 
            
            # Update the idx of nearest bad relationship (nums[i-1]<nums[i])
            if nums[i-1] < nums[i]:
                last_idx_larger_than_prev = i
                
                
        # Use the symmetry.
        # If we horizontally flip the "previous k non-increasing" of nums[::-1],
        # we can get "posterior k non-increasing" of nums.
        rev_nums = nums[::-1]
        last_idx_larger_than_prev = -1  # Record last i such that nums[i-1] < nums[i]
        tmp_posterior_k_non_decr = [True] * n
        for i in range(n):
            if i == 0:
                continue
                
            if last_idx_larger_than_prev >= i - k + 1:
                tmp_posterior_k_non_decr[i] = False
            
            if rev_nums[i-1] < rev_nums[i]:
                last_idx_larger_than_prev = i
                
        posterior_k_non_decr = tmp_posterior_k_non_decr[::-1]
        
            
        ans = []
        for i in  range(k, n - k):
            if posterior_k_non_decr[i] and previous_k_non_incr[i]:
                ans.append(i)
                
        return ans       

#############################################################################################

def get_previous_k_non_incr(n, nums, k):
    # previous k non-increasing
    last_idx_larger_than_prev = None  # Record last i such that nums[i-1] < nums[i]
    previous_k_non_incr = [True] * n
    for i in range(1,n):
        # If the bad relationship (nums[i-1]<nums[i]) is too near,
        # it fails to meet:
        # "The k elements that are just before the index i are in non-increasing order."
        if last_idx_larger_than_prev is not None \
        and last_idx_larger_than_prev >= i - k + 1:
            previous_k_non_incr[i] = False 

        # Update the idx of nearest bad relationship (nums[i-1]<nums[i])
        if nums[i-1] < nums[i]:
            last_idx_larger_than_prev = i
    return previous_k_non_incr

class Solution:
    def goodIndices(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        
        previous_k_non_incr = get_previous_k_non_incr(n, nums, k)
        posterior_k_non_decr = get_previous_k_non_incr(n, nums[::-1], k)[::-1]
            
        ans = []
        for i in  range(k, n - k):
            if posterior_k_non_decr[i] and previous_k_non_incr[i]:
                ans.append(i)
                
        return ans