# was able to rewrite your solution that's more understandable to me def minimumMountainRemovals(self, nums: List[int]) -> int: n = len(nums) lis = [1] * n for r in range(1, n): for l in range(r): if nums[r] > nums[l]: lis[r] = max(lis[r], lis[l] + 1) lds = [1] * n for r in range(n - 2, -1, -1): for l in range(n - 1, r, -1): if nums[r] > nums[l]: lds[r] = max(lds[r], lds[l] + 1) max_mountain = 0 for i in range(1, n - 1): if lis[i] > 1 and lds[i] > 1: cur_mountain = lis[i] + lds[i] - 1 max_mountain = max(max_mountain, cur_mountain) return n - max_mountain
Additional optimization to papa NeetCode's solution would be to put the LIS and result loop together because their loop starts and ends on the same index. def minimumMountainRemovals(self, nums: List[int]) -> int: lds = [1 for i in nums] lis = [1 for i in nums] res = len(nums) # Get lds for i in range(len(nums)-2, 0, -1): cur_max = 1 for j in range(i+1, len(nums)): if nums[i] > nums[j] and lds[j]+1 > cur_max: cur_max = lds[j]+1 lds[i] = cur_max # Get lis and res for i in range(1, len(nums)-1): cur_max = 1 for j in range(i): if nums[i] > nums[j] and lis[j]+1 > cur_max: cur_max = lis[j]+1 lis[i] = cur_max # Calc res if cur_max != 1 and lds[i] != 1: calc = len(nums)-cur_max-lds[i]+1 res = calc if calc < res else res return res And also because we loop only the required indexes, the resulting code runs faster on 936 ms (69%) on my end.
Papa Neetcode finally posted a new video after 3 days 🥹
This is not the most optimal solution I guess. Why didn't you use Binary search to reduce the time complexity to NlogN?
# was able to rewrite your solution that's more understandable to me
def minimumMountainRemovals(self, nums: List[int]) -> int:
n = len(nums)
lis = [1] * n
for r in range(1, n):
for l in range(r):
if nums[r] > nums[l]:
lis[r] = max(lis[r], lis[l] + 1)
lds = [1] * n
for r in range(n - 2, -1, -1):
for l in range(n - 1, r, -1):
if nums[r] > nums[l]:
lds[r] = max(lds[r], lds[l] + 1)
max_mountain = 0
for i in range(1, n - 1):
if lis[i] > 1 and lds[i] > 1:
cur_mountain = lis[i] + lds[i] - 1
max_mountain = max(max_mountain, cur_mountain)
return n - max_mountain
Additional optimization to papa NeetCode's solution would be to put the LIS and result loop together because their loop starts and ends on the same index.
def minimumMountainRemovals(self, nums: List[int]) -> int:
lds = [1 for i in nums]
lis = [1 for i in nums]
res = len(nums)
# Get lds
for i in range(len(nums)-2, 0, -1):
cur_max = 1
for j in range(i+1, len(nums)):
if nums[i] > nums[j] and lds[j]+1 > cur_max:
cur_max = lds[j]+1
lds[i] = cur_max
# Get lis and res
for i in range(1, len(nums)-1):
cur_max = 1
for j in range(i):
if nums[i] > nums[j] and lis[j]+1 > cur_max:
cur_max = lis[j]+1
lis[i] = cur_max
# Calc res
if cur_max != 1 and lds[i] != 1:
calc = len(nums)-cur_max-lds[i]+1
res = calc if calc < res else res
return res
And also because we loop only the required indexes, the resulting code runs faster on 936 ms (69%) on my end.
Coders, is leetCode running so slowly right now ?? I can't even open my profile page
And thx a lot neetCode!!
One of the best explanations out there! Thank you so much for doing this!
This was hard! but nice explanation.
The peak of leetcode
Love you Neet ❤
Did it using 2 LIS arrays
Thanks
Smooth
Holy hard!