Daily Leetcode Challenge | Day 30 | HARD | Minimum Number of Removals to Make Mountain Array

[@darshankumar5546]

#Space complexity= O(n)
# TIme complexity=O(n2)
class Solution:
def minimumMountainRemovals(self, nums: List[int]) -> int:
n=len(nums)
#Longest Increasing Subsequence (LIS)
lis=[1 for i in range(n)]
#Longest Decreasing Subsequence (LDS)
lds=[1 for i in range(n)]
# calculate LIS
for i in range(1,n-1):
for j in range(i):
if(nums[i]>nums[j]):
lis[i]=max(lis[i],lis[j]+1)
print(lis)
# calculate LDS
for i in range(n-2,0,-1):
for j in range(n-1,i,-1):
if(nums[i]>nums[j]):
lds[i]=max(lds[i],lds[j]+1)
print(lds)
#finding best peak
minEleToRemove=n
for i in range(1,n-1):
if(lis[i]>1 and lds[i]>1):
# i can be peak only if there is atleast 1 ele, to its LEFT, which is smaller
# i can be peak only if there is atleast 1 ele, to its RIGHT, which is smaller
#when 'i' is peak, calculate how may ele needs to be removed
NoOfEleToBeRemoved=(i+1-lis[i])+(n-i-lds[i])
minEleToRemove=min(minEleToRemove,NoOfEleToBeRemoved)

return minEleToRemove
# nums=[1,5,3]
# LIS=[1,2,2]
# LDS=[1,2,1]

[@darshankumar5546]

Watch at 0.75X speed, if you are watching my videos for 1st time.😅.