Minimum Number of Removals to Make Mountain Array - Leetcode 1671 - Python

0:00 - Read the problem
0:30 - Intuition
10:12 - Drawing Example
5:05 - Coding Explanation

leetcode 1671

#neetcode #leetcode #python

[jamestariga]

Papa Neetcode finally posted a new video after 3 days 🥹

[gabrieldavi]

Hi Neetcode! I got an offer from Uber!
I would never be able to pass their interview without your videos. Keep it up!

[Kaviarasu_NS]

# 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

[LasTCursE]

The way I did it is by defining two right pointers and two left pointers (the left ones are from the nested loops themselves) and I updated the right ones as we went along. This way, you can use a single nested loop instead of doing it twice :)

It's a bit harder to read, but works faster

let rp1 = arr.length - 2;
let rp2 = arr.length - 1;


for (let lp1 = 1; lp1 < arr.length; lp1++) {
for (let lp2 = 0; lp2 < lp1; lp2++) {
if (arr[lp2] < arr[lp1]) { increase[lp1] = Math.max(increase[lp1], increase[lp2] + 1); }
if (rp1 >= 0 && rp2 > rp1 && arr[rp2] < arr[rp1]) { decrease[rp1] = Math.max(decrease[rp1], decrease[rp2] + 1)}
rp2--;
}
rp1--;
rp2 = arr.length - 1;
}

[victoriatfarrell]

Good advice. Don't get discouraged -- there's always an opportunity to learn and appreciate.

[AlfredPros]

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.

[osamahussam]

Coders, is leetCode running so slowly right now ?? I can't even open my profile page
And thx a lot neetCode!!

[MP-nyep]

One of the best explanations out there! Thank you so much for doing this!

[jaatharsh]

wonderfull as always, thanks for gr8 explanation

[nirmalgurjar]

Bruteforce would be backtracking, generating all subseq and checking each subseq if its mountain and return its size, but time complexity would be n * 2^n then we can try bottom up dp LIS / LDS and come up n*n solution.

[Pyramid-ycex]

Hi, Love your videos, they are very helpful!!!

Have you tried to use Open AI O1 model since it was released? I would like to hear your thoughts/comments on its code generation capabilities. Thanks!!

[Friendforu]

I am thinking to include ur photo in my prayer room 😁, good explanattion bro

[maheshkaranam]

Complex codes made easy. Super sir.
Can you suggest some books to learn complete DSA ?
I wonder how you learnt DSA. could you please answer ?

[muntajir]

This is not the most optimal solution I guess. Why didn't you use Binary search to reduce the time complexity to NlogN?

[WebSleek]

Hii Neetcode I has able to come up with LIS and LDS solution but in editorial there are other approaches also
do i really need to go through them or if i am able to solve it then it good go ahead ?
pls help me out !!!

[abhinavnarula]

Similar to Longest Bitonic subsequence if anyone wants to practice similar kind of a problem.

[samarthjain]

Should have also included the O(Nlog(N)) solution using Binary Search.

[pastori]

im saving the neetcode 150 for when i actually get an interview

[adityaagarwal-iihv]

why are the code solutions removed form website?

[akialter]

It will be a pro gamer move if they let yesterday problem LIS